Back to DSA

Critical Connections in a Network

hard
Acceptance: 44%
GraphsDFS

A network of n nodes is connected by undirected edges. A bridge is an edge whose removal would disconnect the graph. Identify all bridges in the given network.

Examples

Example 1:
Input:n = 5, connections = [[0,1],[1,2],[2,0],[1,3],[3,4]]
Output:[[1,3],[3,4]]
Explanation: Removing either edge [1,3] or [3,4] disconnects node 3 or 4 from the rest. The edges in the cycle 0-1-2 are not bridges.

Hints

Related Problems

Clone GraphmediumPacific Atlantic Water FlowmediumRotting OrangesmediumWalls and GatesmediumShortest Path in Binary Matrixmedium
00:00
import java.util.*;

class Solution {
    private int timer = 0;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (List<Integer> c : connections) {
            graph.get(c.get(0)).add(c.get(1));
            graph.get(c.get(1)).add(c.get(0));
        }
        int[] disc = new int[n], low = new int[n];
        Arrays.fill(disc, -1);
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, -1, disc, low, graph, result);
        return result;
    }

    private void dfs(int u, int parent, int[] disc, int[] low, List<List<Integer>> graph, List<List<Integer>> result) {
        disc[u] = low[u] = timer++;
        for (int v : graph.get(u)) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                dfs(v, u, disc, low, graph, result);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) result.add(Arrays.asList(u, v));
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}
Time complexityO(V + E)
Space complexityO(V + E)