Problem Description

You are given an undirected network of n servers labeled from 0 to n-1 and a list of connections where each connection is a pair of servers [a, b] representing a direct connection between servers a and b.

A critical connection is a connection that, if removed, will make some server(s) unable to reach some other server(s) (i.e., the network becomes disconnected).

Your task is to find all such critical connections in the network. The answer can be returned in any order.

• There is exactly one unique solution for the network.
• Each connection is bidirectional and used at most once.
• The network is connected before any removal.

Example:
n = 4
connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]

Thought Process

The problem is essentially about finding all bridges in an undirected graph. A bridge is an edge that, if removed, increases the number of connected components in the graph.

The brute-force approach would be to remove each edge one by one, and check if the graph is still connected (using BFS or DFS). However, this is inefficient for large graphs, as each connectivity check is expensive.

To optimize, we need a way to find all bridges efficiently. This leads us to graph algorithms like Tarjan's Algorithm for finding bridges in O(N + E) time. The core idea is to use DFS traversal and keep track of the discovery time and the lowest point reachable from each node.

In summary, the shift is from a naive "try everything" approach to a clever, single-pass DFS that efficiently identifies critical edges.

Solution Approach

We use Tarjan's Algorithm to find all bridges in the undirected graph. Here's how it works step by step:

1. Build the Graph:
   • Use an adjacency list to represent the connections between servers. This allows efficient traversal.
2. Initialize Tracking Arrays:
   • disc: Discovery time of each node (when it's first visited).
   • low: The earliest discovered node reachable from the current node (including itself and its descendants).
   • Both arrays help us detect if an edge is a bridge.
3. DFS Traversal:
   • Start DFS from any node (say, node 0), keeping track of the parent to avoid revisiting the immediate ancestor.
   • For each neighbor, recursively perform DFS if it hasn't been visited.
   • After returning from DFS, update the low value of the current node.
4. Bridge Condition:
   • If low[neighbor] > disc[current], then the edge between current and neighbor is a bridge (i.e., a critical connection).
5. Result Collection:
   • Collect all such edges and return them as the result.

The algorithm visits each node and edge only once, making it efficient for large graphs.

Example Walkthrough

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

1. Build the Graph:
   • 0: [1,2]
   • 1: [0,2,3]
   • 2: [0,1]
   • 3: [1]
2. Start DFS at node 0:
   • Visit 0, disc[0]=0, low[0]=0
   • Go to 1 (neighbor of 0): disc[1]=1, low[1]=1
   • From 1, go to 2: disc[2]=2, low[2]=2
   • From 2, neighbors are 0 (parent, skip) and 1 (already visited, skip)
   • Backtrack: Update low[1] = min(low[1], low[2]) = 1
   • From 1, go to 3: disc[3]=3, low[3]=3
   • From 3, neighbor is 1 (parent, skip)
   • Backtrack: low[1] = min(low[1], low[3]) = 1
3. Bridge Detection:
   • Edge [1,3]: low[3]=3 > disc[1]=1 ⇒ bridge
   • Other edges: low[2]=1, disc[1]=1 and low[1]=0, disc[0]=0 (not a bridge)
4. Result: [[1,3]]

Thus, only the edge [1,3] is a critical connection; removing it disconnects node 3 from the network.

Time and Space Complexity

• Brute-force:
  • For each edge, remove it and check connectivity (using BFS/DFS): O(E*(N+E))
  • Highly inefficient for large graphs.
• Optimized (Tarjan's Algorithm):
  • DFS visits each node and edge once: O(N + E)
  • Space: O(N + E) for adjacency list and tracking arrays.

The optimized approach is efficient and scalable for large networks.

Summary

We tackled the problem of finding critical connections in a network by reducing it to finding bridges in an undirected graph. While brute-force is slow, Tarjan's Algorithm provides an elegant and efficient way to find all such edges in a single DFS traversal. By keeping track of discovery and low times, we can precisely identify which connections are critical, ensuring the network stays connected.

Code Implementation

class Solution:
    def criticalConnections(self, n, connections):
        from collections import defaultdict
        graph = defaultdict(list)
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        disc = [-1] * n
        low = [-1] * n
        res = []
        time = [0]
        
        def dfs(u, parent):
            disc[u] = low[u] = time[0]
            time[0] += 1
            for v in graph[u]:
                if v == parent:
                    continue
                if disc[v] == -1:
                    dfs(v, u)
                    low[u] = min(low[u], low[v])
                    if low[v] > disc[u]:
                        res.append([u, v])
                else:
                    low[u] = min(low[u], disc[v])
        
        dfs(0, -1)
        return res
      

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> graph(n);
        for (auto& conn : connections) {
            graph[conn[0]].push_back(conn[1]);
            graph[conn[1]].push_back(conn[0]);
        }
        vector<int> disc(n, -1), low(n, -1);
        vector<vector<int>> res;
        int time = 0;
        function<void(int, int)> dfs = [&](int u, int parent) {
            disc[u] = low[u] = time++;
            for (int v : graph[u]) {
                if (v == parent) continue;
                if (disc[v] == -1) {
                    dfs(v, u);
                    low[u] = min(low[u], low[v]);
                    if (low[v] > disc[u]) {
                        res.push_back({u, v});
                    }
                } else {
                    low[u] = min(low[u], disc[v]);
                }
            }
        };
        dfs(0, -1);
        return res;
    }
};
      

class Solution {
    private int time = 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> conn : connections) {
            graph.get(conn.get(0)).add(conn.get(1));
            graph.get(conn.get(1)).add(conn.get(0));
        }
        int[] disc = new int[n];
        int[] low = new int[n];
        Arrays.fill(disc, -1);
        Arrays.fill(low, -1);
        List<List<Integer>> res = new ArrayList<>();
        dfs(0, -1, disc, low, graph, res);
        return res;
    }
    private void dfs(int u, int parent, int[] disc, int[] low, List<List<Integer>> graph, List<List<Integer>> res) {
        disc[u] = low[u] = time++;
        for (int v : graph.get(u)) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                dfs(v, u, disc, low, graph, res);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    res.add(Arrays.asList(u, v));
                }
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}
      

var criticalConnections = function(n, connections) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const disc = Array(n).fill(-1);
    const low = Array(n).fill(-1);
    let time = 0;
    const res = [];
    function dfs(u, parent) {
        disc[u] = low[u] = time++;
        for (const v of graph[u]) {
            if (v === parent) continue;
            if (disc[v] === -1) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    res.push([u, v]);
                }
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
    dfs(0, -1);
    return res;
};