Critical Connections
In a given graph, a critical connection is an edge that, when removed, increases the number of connected components in the graph. Given a graph with n nodes and edges, find all critical connections.
Constraints:
- 1 <= n <= 10^4
- 0 <= edges.length <= 10^4
- edges[i].length == 2
- 0 <= edges[i][0] < n
- 0 <= edges[i][1] < n
- edges[i][0] != edges[i][1]
Examples:
Input: [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: The edge between nodes 1 and 3 is a critical connection because removing it increases the number of connected components in the graph.
Solutions
Tarjan's Algorithm
Tarjan's algorithm is used to find all critical connections in the graph. The algorithm works by performing a depth-first search (DFS) on the graph and keeping track of the discovery time and low value for each node. The low value of a node is the smallest discovery time of any node that is reachable from the current node. If the low value of a node is greater than the discovery time of its parent, then the edge between the node and its parent is a critical connection.
public List<List<Integer>> criticalConnections(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0;
i < n;
i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
int[] low = new int[n];
int[] disc = new int[n];
int time = 0;
List<List<Integer>> result = new ArrayList<>();
for (int i = 0;
i < n;
i++) {
if (disc[i] == 0) {
dfs(graph, i, -1, disc, low, result, time);
}
}
return result;
}
private void dfs(List<List<Integer>> graph, int node, int parent, int[] disc, int[] low, List<List<Integer>> result, int[] time) {
disc[node] = low[node] = time[0]++;
for (int neighbor : graph.get(node)) {
if (disc[neighbor] == 0) {
dfs(graph, neighbor, node, disc, low, result, time);
low[node] = Math.min(low[node], low[neighbor]);
if (low[neighbor] > disc[node]) {
result.add(Arrays.asList(node, neighbor));
}
}
else if (neighbor != parent) {
low[node] = Math.min(low[node], disc[neighbor]);
}
}
}Follow-up:
Find all critical connections in a directed graph.
