Comment on page

# 1192.Critical-Connections-in-a-Network

## 题目描述

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.
Constraints:
1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i] != connections[i]
There are no repeated connections.

## 代码

### Approach 1: Tarjan

An edge is a critical connection, if and only if it is not in a cycle.
class Solution {
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
int time = 0;
int[] low = new int[n];
int[] disc = new int[n];
boolean[] visited = new boolean[n];
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
}
for (List<Integer> node : connections) {
}
// 2. dfs
dfs(0, -1, time, adj, low, disc, visited, ans);
return ans;
}
private void dfs(int current , int parent, int time, List<Integer>[] adj, int[] low, int[] disc, boolean[] visited, List<List<Integer>> ans) {
time++;
low[current] = time;
disc[current] = time;
visited[current] = true;
if (neighbor == parent) continue;
if (visited[neighbor] == false) {
dfs(neighbor, current, time, adj, low, disc, visited, ans);
low[current] = Math.min(low[current], low[neighbor]);
// If the lowest vertex reachable from subtree
// under neighbor is below current in DFS tree, then current-neighbor is a bridge
if (low[neighbor] > disc[current]) {
}
} else {
low[current] = Math.min(low[current], disc[neighbor]); // ?? => low[neighbor]
}
}
}
}

### #2

private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (List<Integer> c: connections) {
}
int[] timestamps = new int[n];
dfs(graph, 0, 0, 1, timestamps);
return ans;
}
private int dfs(Map<Integer, List<Integer>> graph, int curr, int parent, int currTimestamp, int[] timestamps) {
timestamps[curr] = currTimestamp;
for (int nextNode : graph.getOrDefault(curr, new ArrayList<Integer>())) {
if (nextNode == parent) continue;
if (timestamps[nextNode] > 0) {
timestamps[curr] = Math.min(timestamps[curr], timestamps[nextNode]);
} else {
timestamps[curr] = Math.min(timestamps[curr],
dfs(graph, nextNode, curr, currTimestamp + 1, timestamps));
}
if (currTimestamp < timestamps[nextNode]) {