🖥️ 连通网络的操作次数
📝 题目描述
用以太网线缆将n台计算机连接成一个网络，计算机的编号从0到n-1。线缆用connections表示，其中connections[i] = [a,b]连接了计算机a和b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线connections，你可以拨开任意两台计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回-1。
📋 代码模板
java
class Solution {
public int makeConnected(int n, int[][] connections) {
}
}typescript
function makeConnected(n: number, connections: number[][]): number {
}💡 提示
- 没有重复的连接
- 两台计算机不会通过多条线缆连接
🚀 示例
🖊️ 题解
DFS
可惜没有如果
java
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> paths = new ArrayList<>();
dfs(graph, paths, new ArrayList<>(), 0);
return paths;
}
private void dfs(int[][] graph, List<List<Integer>> paths, List<Integer> path, int i) {
path.add(i);
if (i == graph.length - 1) {
paths.add(new ArrayList<>(path));
path.remove(path.size() - 1);
return;
}
for (int next : graph[i]) {
dfs(graph, paths, path, next);
}
path.remove(path.size() - 1);
}
}typescript
function allPathsSourceTarget(graph: number[][]): number[][] {
const paths: number[][] = [];
dfs(graph, paths, [], 0);
return paths;
}
function dfs(graph: number[][], paths: number[][], path: number[], i: number): void {
path.push(i);
if (i == graph.length - 1) {
paths.push([...path]);
path.pop();
return;
}
for (const next of graph[i]) {
dfs(graph, paths, path, next);
}
path.pop();
}BFS
如果没有
java
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int n = graph.length;
Queue<List<Integer>> queue = new LinkedList<>();
List<Integer> startPath = new ArrayList<>();
startPath.add(0);
queue.offer(startPath);
List<List<Integer>> paths = new ArrayList<>();
while (!queue.isEmpty()) {
List<Integer> originalPath = queue.poll();
int i = originalPath.get(originalPath.size() - 1);
if (i == n - 1) {
paths.add(originalPath);
continue;
}
for (int next : graph[i]) {
List<Integer> path = new ArrayList<>(originalPath);
path.add(next);
queue.offer(path);
}
}
return paths;
}
}typescript
function allPathsSourceTarget(graph: number[][]): number[][] {
const n = graph.length;
const queue: number[][] = [];
queue.push([0]);
const paths: number[][] = [];
while (queue.length > 0) {
const originalPath: number[] = queue.shift()!;
const i = originalPath[originalPath.length - 1];
if (i == n - 1) {
paths.push(originalPath);
continue;
}
for (const next of graph[i]) {
const path: number[] = [...originalPath];
path.push(next);
queue.push(path);
}
}
return paths;
}