There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some servers unable to reach some other server.
Return all critical connections in the network in any order.
Example 1:
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.
Example 2:
Input: n = 2, connections = [[0,1]] Output: [[0,1]]
有没有回路都可以有关键路径
Tarjan算法：时间戳判断-有没有回路，这只是一个辅助工具。结果大小用于判断是否这个节点唯一的neighbor就是parent
//https://leetcode.com/problems/critical-connections-in-a-network/discuss/399827/Java-DFS-Solution-similar-to-Tarjan-maybe-easier-to-understand
class Solution {
int T = 1;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
// use a timestamp, for each node, check the samllest timestamp that can reach from the node
// construct the graph first
List[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<Integer>();
}
for (List<Integer> conn : connections) {
graph[conn.get(0)].add(conn.get(1));
graph[conn.get(1)].add(conn.get(0));
}
int[] timestamp = new int[n]; // an array to save the timestamp that we meet a certain node
// for each node, we need to run dfs for it, and return the smallest timestamp in all its children except its parent
List<List<Integer>> criticalConns = new ArrayList<>();
dfs(n, graph, timestamp, 0, -1, criticalConns);
return criticalConns;
}
// return the minimum timestamp it ever visited in all the neighbors
private int dfs(int n, List[] graph, int[] timestamp, int i, int parent, List<List<Integer>> criticalConns) {
if (timestamp[i] != 0) return timestamp[i];
timestamp[i] = T++;
int minTimestamp = Integer.MAX_VALUE;
for (int neighbor : (List<Integer>) graph[i]) {
if (neighbor == parent) continue; // no need to check the parent
//关键路径：一删掉就断联的路径
//3这个节点唯一的neighbor就是parent1，所以会continue掉。
//后面会反常，所以输出。
int neighborTimestamp = dfs(n, graph, timestamp, neighbor, i, criticalConns);
//除了parent节点外，所有邻居节点中的最小值。
//因为是一路过来的，所以理应比现在的timestamp[i]更小
minTimestamp = Math.min(minTimestamp, neighborTimestamp);
}
if (minTimestamp >= timestamp[i]) {
System.out.println("此时添加");
System.out.println("minTimestamp = " + minTimestamp);
System.out.println("timestamp[i] = " + timestamp[i]);
System.out.println("parent = " + parent);
System.out.println("i = " + i);
System.out.println(" ");
if (parent >= 0) criticalConns.add(Arrays.asList(parent, i));
}
return Math.min(timestamp[i], minTimestamp);
}
}
//
4
[[0,1],[1,2],[2,0],[1,3]]
此时添加
minTimestamp = 2147483647
timestamp[i] = 4
parent = 1
i = 3
此时添加
minTimestamp = 1
timestamp[i] = 1
parent = -1
i = 0