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

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/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][0] != connections[i][1]
There are no repeated connections.``````

## ไปฃ็ 

### Approach 1: Tarjan

An edge is a critical connection, if and only if it is not in a cycle.

https://zhuanlan.zhihu.com/p/101923309

``````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]) {