查找集群内的关键连接
难度:
标签:
题目描述
力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。用 connections 表示集群网络，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
关键连接 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。
请你以任意顺序返回该集群内的所有 关键连接 。
示例 1：
输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] 输出：[[1,3]] 解释：[[3,1]] 也是正确的。
示例 2:
输入：n = 2, connections = [[0,1]] 输出：[[0,1]]
提示：
2 <= n <= 105n - 1 <= connections.length <= 1050 <= ai, bi <= n - 1ai != bi- 不存在重复的连接
代码结果
运行时间: 305 ms, 内存: 60.2 MB
// 思路：与传统Java实现类似，这里依然使用Tarjan算法。我们用Stream来处理输入并输出结果。
// 但由于DFS的递归特性，核心算法部分并没有使用Stream来替代。
import java.util.*;
import java.util.stream.Collectors;
public class CriticalConnectionsStream {
private int time = 0;
private List<List<Integer>> result = new ArrayList<>();
private int[] ids, low;
private List<Integer>[] graph;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
connections.forEach(conn -> {
graph[conn.get(0)].add(conn.get(1));
graph[conn.get(1)].add(conn.get(0));
});
ids = new int[n];
low = new int[n];
Arrays.fill(ids, -1);
for (int i = 0; i < n; i++) {
if (ids[i] == -1) {
dfs(i, -1);
}
}
return result.stream().collect(Collectors.toList());
}
private void dfs(int u, int parent) {
ids[u] = low[u] = ++time;
for (int v : graph[u]) {
if (v == parent) continue;
if (ids[v] == -1) { // v is not visited
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > ids[u]) {
result.add(Arrays.asList(u, v));
}
} else {
low[u] = Math.min(low[u], ids[v]);
}
}
}
}
解释
方法:
这个题解使用了Tarjan算法来查找无向图中的桥（关键连接）。该算法通过深度优先搜索（DFS）来遍历图，并使用一个数组ids来记录每个节点在DFS树中的编号。对于每个节点，我们用它的编号初始化ids数组，然后在DFS过程中更新ids值。如果一个节点的编号等于它在ids数组中的值，且它不是根节点，那么该节点与它的父节点之间的边就是一座桥。这是因为从根节点到该节点的路径上没有其他路径可以到达该节点。
时间复杂度:
O(V+E)
空间复杂度:
O(V+E)
代码细节讲解
🦆
在Tarjan算法中，为什么需要使用一个数组ids来记录每个节点在DFS树中的编号？
▷🦆
你是如何处理图中可能存在的环的情况？在这种情况下，算法的行为是怎样的？
▷🦆
题解中提到，如果一个节点的编号等于它在ids数组中的值，并且它不是根节点，这条边就是桥。能否详细解释为什么满足这两个条件的边会是桥？
▷🦆
题解中的 `dfs` 函数递归调用时，cur_id参数递增，这是基于什么考虑？增加cur_id的作用是什么？
▷