1192. Critical Connections in a Network Solution

The problem

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a_i, b_i] represents a connection between servers a_i and b_i. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

Constraints:

2 <= n <= 10⁵
n - 1 <= connections.length <= 10⁵
0 <= a_i, b_i <= n - 1
a_i != b_i
There are no repeated connections.

Approach overview

Problem Overview: You are given n servers connected by bidirectional edges. A connection is critical if removing it disconnects part of the network. The task is to return all such edges, also known as bridges in graph theory.

Approach 1: Edge Removal + Connectivity Check (Brute Force) (Time: O(E * (V + E)), Space: O(V + E))

Remove each edge one at a time and run a DFS or BFS to check whether the graph is still fully connected. If the number of reachable nodes decreases, that edge is a critical connection. Implementation is straightforward: build the adjacency list, temporarily skip the tested edge, then run a traversal from any node. This approach works for small graphs but becomes expensive because you repeat a full traversal for every edge.

Approach 2: Union-Find Connectivity Testing (Time: O(E² α(V)), Space: O(V))

Another option rebuilds connectivity using a Union-Find structure for each edge exclusion. For every edge (u, v), rebuild the disjoint set using all other edges and check whether u and v remain connected. Path compression and union by rank make each union nearly constant time, but rebuilding the structure repeatedly still leads to quadratic behavior. This approach helps demonstrate connectivity reasoning but is rarely the optimal bridge detection method.

Approach 3: DFS with Tarjan's Algorithm (Optimal) (Time: O(V + E), Space: O(V))

The optimal solution uses a single Depth-First Search traversal combined with Tarjan's bridge-finding technique. Each node records two values: its discovery time and the lowest discovery time reachable through its subtree (low). While exploring neighbors, update the low-link values using back edges. If for an edge (u, v) the condition low[v] > disc[u] holds, there is no alternative path from v back to u or its ancestors, meaning the edge is a bridge. This method processes every vertex and edge exactly once, making it linear time. It is a standard technique in graph problems involving bridges and biconnected components.

Recommended for interviews: Interviewers expect the Tarjan DFS solution because it demonstrates strong graph fundamentals and understanding of bridge detection. Mentioning the brute force edge-removal idea first shows problem intuition, but implementing the linear-time Tarjan approach signals deeper algorithmic skill.

Approach 1: Depth-First Search (DFS) and Tarjan's Algorithm

This approach leverages Tarjan's Algorithm to find bridges in an undirected graph. A bridge, also known as a critical connection, is an edge which, when removed, increases the number of connected components in a graph.

The main idea is to use a DFS traversal while keeping track of two things for each node:

Discovery time: The time when a node is first visited.
Lowest point: The smallest discovery time reachable from the node, including itself or its descendants.

During the DFS traversal, if a node discovers a node that was discovered earlier, we update the current node's lowest point based on the discovered node unless it is a direct parent of the current node which means it's a backtracking edge. If the lowest point of the descendant is greater than the discovery time of the current node, then the connection between them is a critical connection.

Python

def criticalConnections(n, connections):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)

    low = [-1] * n    
    disc = [-1] * n   
    parent = [-1] * n
    critical_edges = []
    time = 0

    def dfs(u):
        nonlocal time
        disc[u] = low[u] = time
        time += 1

        for v in graph[u]:
            if disc[v] == -1:  
                parent[v] = u
                dfs(v)

                low[u] = min(low[u], low[v])

                if low[v] > disc[u]:
                    critical_edges.append([u, v])
            elif v != parent[u]:  
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i)

    return critical_edges

Java

import java.util.*;

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (List<Integer> connection : connections) {
            graph.computeIfAbsent(connection.get(0), k -> new ArrayList<>()).add(connection.get(1));
            graph.computeIfAbsent(connection.get(1), k -> new ArrayList<>()).add(connection.get(0));
        }

        int[] low = new int[n];
        int[] disc = new int[n];
        Arrays.fill(disc, -1);
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        int time = 0;

        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) {
                dfs(i, time, low, disc, parent, graph, result);
            }
        }
        return result;
    }

    private void dfs(int u, int time, int[] low, int[] disc, int[] parent, Map<Integer, List<Integer>> graph, List<List<Integer>> result) {
        disc[u] = low[u] = time++;

        for (int v : graph.getOrDefault(u, Collections.emptyList())) {
            if (disc[v] == -1) {
                parent[v] = u;
                dfs(v, time, low, disc, parent, graph, result);

                low[u] = Math.min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    result.add(Arrays.asList(u, v));
                }
            } else if (v != parent[u]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}

C++

#include <vector>
#include <unordered_map>
#include <list>
using namespace std;

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> result;
        vector<int> low(n, -1);
        vector<int> disc(n, -1);
        vector<int> parent(n, -1);
        int time = 0;

        unordered_map<int, list<int>> graph;
        for (const auto& conn : connections) {
            graph[conn[0]].push_back(conn[1]);
            graph[conn[1]].push_back(conn[0]);
        }

        for (int i = 0; i < n; ++i) {
            if (disc[i] == -1) {
                dfs(i, time, low, disc, parent, graph, result);
            }
        }
        return result;
    }

    void dfs(int u, int& time, vector<int>& low, vector<int>& disc, vector<int>& parent,
             unordered_map<int, list<int>>& graph, vector<vector<int>>& result) {
        disc[u] = low[u] = time++;

        for (int v : graph[u]) {
            if (disc[v] == -1) {
                parent[v] = u;
                dfs(v, time, low, disc, parent, graph, result);

                low[u] = min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    result.push_back({u, v});
                }
            } else if (v != parent[u]) {
                low[u] = min(low[u], disc[v]);
            }
        }
    }
};

JavaScript

var criticalConnections = function(n, connections) {
    const graph = new Map();
    const buildGraph = (connections) => {
        connections.forEach(([u, v]) => {
            if (!graph.has(u)) graph.set(u, []);
            if (!graph.has(v)) graph.set(v, []);
            graph.get(u).push(v);
            graph.get(v).push(u);
        });
    };

    buildGraph(connections);

    const disc = new Array(n).fill(-1);
    const low = new Array(n).fill(-1);
    const criticalEdges = [];
    let time = 0;

    const dfs = (u, parent) => {
        disc[u] = low[u] = time++;

        for (let v of graph.get(u)) {
            if (disc[v] === -1) {
                dfs(v, u);

                low[u] = Math.min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    criticalEdges.push([u, v]);
                }
            } else if (v !== parent) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (disc[i] === -1) {
            dfs(i, -1);
        }
    }

    return criticalEdges;
};

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections) {
        var graph = new Dictionary<int, List<int>>();
        foreach (var edge in connections) {
            if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List<int>();
            if (!graph.ContainsKey(edge[1])) graph[edge[1]] = new List<int>();
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        var result = new List<IList<int>>();
        int[] low = new int[n];
        int[] disc = new int[n];
        Array.Fill(disc, -1);
        var parent = new int[n];
        Array.Fill(parent, -1);
        int time = 0;

        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) {
                DFS(i, time, low, disc, parent, graph, result);
            }
        }
        return result;
    }

    private void DFS(int u, ref int time, int[] low, int[] disc, int[] parent,
                     Dictionary<int, List<int>> graph, List<IList<int>> result) {
        disc[u] = low[u] = time++;

        foreach (int v in graph[u]) {
            if (disc[v] == -1) {
                parent[v] = u;
                DFS(v, ref time, low, disc, parent, graph, result);

                low[u] = Math.Min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    result.Add(new List<int> { u, v });
                }
            } else if (v != parent[u]) {
                low[u] = Math.Min(low[u], disc[v]);
            }
        }
    }
}

The code defines a function criticalConnections which constructs a graph from the given connections. It uses DFS traversal to calculate the disc and low values. The critical connections are collected in critical_edges list.

Complexity

The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is also O(V + E) due to the graph representation and recursion stack.

Try this approach in the editor

Approach 2: Union-Find with Path Compression

The Union-Find approach is less direct for this problem as it better suits static connectivity queries, but it can verify the disconnection effect of removing an edge by checking connectivity before and after its removal.

Here, a variation of Kruskal's algorithm can be employed with additional tracking to retry connections and verify their critical status. However, this requires additional complexity and is not the standard usage for critical connections.

So, while possible, using Union-Find isn't recommended due to its inefficiency in recomputing components with high time complexity.

Python

class UnionFind:
    def __init__(self, size):
        self.root = list(range(size))

    def find(self, x):
        if self.root[x] == x:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.root[rootY] = rootX
            return True
        return False

    def connected(self, x, y):
        return self.find(x) == self.find(y)

def criticalConnections(n, connections):
    result = []
    for i in range(len(connections)):
        modified = connections[:i] + connections[i+1:]
        uf = UnionFind(n)

        for u, v in modified:
            uf.union(u, v)

        if not uf.connected(connections[i][0], connections[i][1]):
            result.append(connections[i])

    return result

C++

#include <vector>
#include <unordered_set>
using namespace std;

class UnionFind {
    vector<int> root;
public:
    UnionFind(int size) {
        root.resize(size);
        for (int i = 0; i < size; ++i) {
            root[i] = i;
        }
    }

    int find(int x) {
        if (root[x] == x) return x;
        return root[x] = find(root[x]);
    }

    bool unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
            return true;
        }
        return false;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> result;

        for (int i = 0; i < connections.size(); ++i) {
            UnionFind uf(n);
            for (int j = 0; j < connections.size(); ++j) {
                if (i == j) continue;
                uf.unionSet(connections[j][0], connections[j][1]);
            }

            if (!uf.connected(connections[i][0], connections[i][1])) {
                result.push_back(connections[i]);
            }
        }
        return result;
    }
};

The code implements a brute-force check of each edge's removal effect by rebuilding a Union-Find structure for each remaining connection set. It provides an intuitive understanding though not efficient for large inputs.

Complexity

The time complexity on worst-case is O(E^2) due to the need for reconstructing the Union-Find structure. The space complexity is O(V) for the Union-Find structure.

Try this approach in the editor

Approach 3: Tarjan Algorithm

The "critical connections" in this problem can be considered as "bridges".

"Bridges": In a connected undirected graph, if removing a certain edge makes the graph disconnected, then this edge can be considered as a "bridge".

Correspondingly, there is also the concept of "articulation points".

"Articulation Points": In a connected undirected graph, if removing a certain point and all edges connected to it makes the graph disconnected, then this point can be considered as an "articulation point".

There is an algorithm called the Tarjan algorithm for finding "bridges" and "articulation points" in a graph. This algorithm uses a depth-first search (DFS) method that first recursively visits adjacent nodes and then visits the node itself. By recording the "order of visit: DFN" and updating the "earliest backtrackable node: low" when visiting the node itself after recursion ends, it can find the "bridges" and "articulation points" of the graph in O(n) time. Also, this algorithm can be used to find strongly connected components in directed graphs.

TypeScript

function criticalConnections(n: number, connections: number[][]): number[][] {
    let now: number = 0;
    const g: number[][] = Array(n)
        .fill(0)
        .map(() => []);
    const dfn: number[] = Array(n).fill(0);
    const low: number[] = Array(n).fill(0);
    for (const [a, b] of connections) {
        g[a].push(b);
        g[b].push(a);
    }
    const ans: number[][] = [];
    const tarjan = (a: number, fa: number) => {
        dfn[a] = low[a] = ++now;
        for (const b of g[a]) {
            if (b === fa) {
                continue;
            }
            if (!dfn[b]) {
                tarjan(b, a);
                low[a] = Math.min(low[a], low[b]);
                if (low[b] > dfn[a]) {
                    ans.push([a, b]);
                }
            } else {
                low[a] = Math.min(low[a], dfn[b]);
            }
        }
    };
    tarjan(0, -1);
    return ans;
}

func criticalConnections(n int, connections [][]int) (ans [][]int) {
	now := 0
	g := make([][]int, n)
	dfn := make([]int, n)
	low := make([]int, n)
	for _, e := range connections {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	var tarjan func(int, int)
	tarjan = func(a, fa int) {
		now++
		dfn[a], low[a] = now, now
		for _, b := range g[a] {
			if b == fa {
				continue
			}
			if dfn[b] == 0 {
				tarjan(b, a)
				low[a] = min(low[a], low[b])
				if low[b] > dfn[a] {
					ans = append(ans, []int{a, b})
				}
			} else {
				low[a] = min(low[a], dfn[b])
			}
		}
	}
	tarjan(0, -1)
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Depth-First Search (DFS) and Tarjan's Algorithm	The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is also O(V + E) due to the graph representation and recursion stack.
Union-Find with Path Compression	The time complexity on worst-case is O(E^2) due to the need for reconstructing the Union-Find structure. The space complexity is O(V) for the Union-Find structure.
Tarjan Algorithm	–

Complexity analysis

Approach	Time	Space	When to Use
Edge Removal + DFS/BFS	O(E * (V + E))	O(V + E)	Conceptual brute force approach for understanding bridges
Union-Find Rebuild per Edge	O(E² α(V))	O(V)	When experimenting with connectivity structures like disjoint sets
DFS with Tarjan's Algorithm	O(V + E)	O(V)	Optimal solution for detecting bridges in undirected graphs

Frequently asked questions

Is Critical Connections in a Network easy or hard?

The problem is rated Hard on LeetCode because it requires understanding Tarjan's algorithm and low-link values. While the DFS traversal itself is straightforward, correctly maintaining discovery times and detecting bridges requires solid graph theory knowledge.

Critical Connections in a Network Python/Java solution

Most implementations use Tarjan's DFS algorithm with adjacency lists. The same logic works across Python, Java, C++, and JavaScript: track discovery time, maintain low values, and record edges where low[v] > disc[u]. This produces all bridges in O(V + E) time.

How to solve Critical Connections in a Network in O(n)?

Solve it with Tarjan's bridge-finding algorithm. Run a DFS while storing discovery times and low-link values for every node. When exploring an edge (u, v), if low[v] becomes greater than disc[u], that edge is a bridge. This processes all vertices and edges once, giving O(V + E) complexity.

What is the best approach for Critical Connections in a Network?

The best approach uses Tarjan's Algorithm with a Depth-First Search. It tracks discovery time and low-link values for each node to identify bridge edges. If low[v] > disc[u], the edge (u, v) is a critical connection. This algorithm runs in O(V + E) time and processes each node and edge once.

Is Critical Connections in a Network asked at Google/Amazon/Meta?

Critical bridge detection problems frequently appear in interviews at companies like Amazon, Google, and Meta because they test deep graph knowledge. Variations often require detecting bridges, articulation points, or biconnected components using DFS-based algorithms.

What data structure is used in Critical Connections in a Network?

The core data structure is an adjacency list representing the graph. The algorithm also uses arrays or lists to store discovery times, low-link values, and visited states during DFS. Some alternative implementations experiment with Union-Find structures for connectivity checks.

What is the time complexity of Critical Connections in a Network?

The optimal Tarjan DFS solution runs in O(V + E) time with O(V) space. Each node is visited once and each edge is examined during the DFS traversal. Brute force approaches that remove edges and recheck connectivity can take O(E * (V + E)) time.

Critical Connections in a Network solution and explanation

The problem

Approach overview

Approach 1: Depth-First Search (DFS) and Tarjan's Algorithm

Approach 2: Union-Find with Path Compression

Approach 3: Tarjan Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments