Critical Connections in a Network

Hard
948.

Critical Connections in a Network

Critical Connections in a Network is a hard coding problem on depth-first search, graph and biconnected component, asked in Amazon, Google and Microsoft interviews.

n CodeKairo servers numbered 0 … n - 1 are joined by undirected connections, forming one network in which every server can reach every other.

A connection is critical if removing it leaves some server unable to reach some other. Return all critical connections, each written as [smaller, larger], sorted in increasing order.

Example 1

Input
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output
[[1,3]]
Explanation
The triangle `0-1-2` survives any single removal; the link to server 3 does not.

Example 2

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

Example 3

Input
n = 3, connections = [[0,1],[1,2],[2,0]]
Output
[]
Explanation
A cycle has no critical connection.

Constraints

  • 2 <= n <= 10^5
  • n - 1 <= connections.length <= 10^5
  • 0 <= connections[i][0], connections[i][1] < n
  • connections[i][0] != connections[i][1]
  • There are no repeated connections.
  • The answer is returned as [smaller, larger] pairs in increasing order.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number[][]}
 */
var criticalConnections = function(n, connections) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Critical Connections in a Network — Problem & Solution

Critical Connections in a Network solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Critical Connections in a Network is a hard coding problem on depth-first search, graph and biconnected component, asked in Amazon, Google and Microsoft interviews.

Problem statement

n CodeKairo servers numbered 0 … n - 1 are joined by undirected connections, forming one network in which every server can reach every other.

A connection is critical if removing it leaves some server unable to reach some other. Return all critical connections, each written as [smaller, larger], sorted in increasing order.

Example 1

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: The triangle `0-1-2` survives any single removal; the link to server 3 does not.

Example 2

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

Example 3

Input: n = 3, connections = [[0,1],[1,2],[2,0]]
Output: []
Explanation: A cycle has no critical connection.

Constraints

  • 2 <= n <= 10^5
  • n - 1 <= connections.length <= 10^5
  • 0 <= connections[i][0], connections[i][1] < n
  • connections[i][0] != connections[i][1]
  • There are no repeated connections.
  • The answer is returned as [smaller, larger] pairs in increasing order.

Hints for Critical Connections in a Network

  1. Hint 1

    A critical connection is a bridge: an edge that lies on no cycle.

  2. Hint 2

    Depth-first search and record, for each node, the earliest discovery time reachable from its subtree.

  3. Hint 3

    Edge (p, u) is a bridge exactly when nothing in u's subtree can reach back past p.

How to solve Critical Connections in a Network

Tarjan's bridge algorithm. During a depth-first search, give each node a discovery time disc and a value low — the earliest discovery time reachable from its subtree using at most one back edge. The tree edge (p, u) is a bridge when low[u] > disc[p].

Approach

  1. Depth-first search from each unvisited node, stamping disc and initialising low to it.
  2. On a tree edge to v, recurse and then low[p] = min(low[p], low[v]).
  3. On a back edge to an already-seen v, low[u] = min(low[u], disc[v]).
  4. Record (p, u) when low[u] > disc[p], then sort the results.

Why it works

low[u] > disc[p] says nothing under u has a second way back to p or above it, so cutting that edge disconnects the subtree — which is exactly what "critical" means. The one subtlety is skipping the edge you arrived on: skipping by neighbour would wrongly ignore a genuine parallel edge, so the search skips the specific edge index instead. The traversal here is written with an explicit stack because n reaches 100 000 and a path-shaped network would overflow the call stack.

Complexity

  • Time — O(n + m)
  • Space — O(n + m)

Pitfalls

  • Comparing low[u] against low[p] instead of disc[p] misses bridges.
  • Skipping every edge back to the parent node hides parallel edges; skip the one edge index.
  • The back-edge update uses disc[v], not low[v].

Reference solution

Python

from typing import List
import sys

def criticalConnections(n: int, connections: List[List[int]]) -> List[List[int]]:
    head = [-1] * n
    cap = max(1, len(connections) * 2)
    nxt = [-1] * cap
    to = [0] * cap
    ec = 0
    for u, v in connections:
        to[ec] = v; nxt[ec] = head[u]; head[u] = ec; ec += 1
        to[ec] = u; nxt[ec] = head[v]; head[v] = ec; ec += 1
    disc = [-1] * n
    low = [0] * n
    timer = 0
    bridges = []
    for s in range(n):
        if disc[s] >= 0:
            continue
        disc[s] = low[s] = timer
        timer += 1
        stack = [(s, -1, head[s])]
        while stack:
            u, in_edge, e = stack[-1]
            if e >= 0:
                stack[-1] = (u, in_edge, nxt[e])
                if in_edge >= 0 and (e ^ 1) == in_edge:
                    continue
                v = to[e]
                if disc[v] < 0:
                    disc[v] = low[v] = timer
                    timer += 1
                    stack.append((v, e, head[v]))
                elif disc[v] < low[u]:
                    low[u] = disc[v]
            else:
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    if low[u] < low[p]:
                        low[p] = low[u]
                    if low[u] > disc[p]:
                        bridges.append([min(p, u), max(p, u)])
    bridges.sort()
    return bridges

Java

public static int[][] criticalConnections(int n, int[][] connections) {
    int[] head = new int[n];
    Arrays.fill(head, -1);
    int cap = Math.max(1, connections.length * 2);
    int[] nxt = new int[cap];
    int[] to = new int[cap];
    int ec = 0;
    for (int[] c : connections) {
        to[ec] = c[1]; nxt[ec] = head[c[0]]; head[c[0]] = ec; ec++;
        to[ec] = c[0]; nxt[ec] = head[c[1]]; head[c[1]] = ec; ec++;
    }
    int[] disc = new int[n];
    int[] low = new int[n];
    Arrays.fill(disc, -1);
    int timer = 0;
    List<int[]> bridges = new ArrayList<>();
    int[] stackNode = new int[n + 1];
    int[] stackEdge = new int[n + 1];
    int[] stackIter = new int[n + 1];
    for (int s = 0; s < n; s++) {
        if (disc[s] >= 0) continue;
        disc[s] = low[s] = timer++;
        int top = 0;
        stackNode[top] = s;
        stackEdge[top] = -1;
        stackIter[top] = head[s];
        top++;
        while (top > 0) {
            int u = stackNode[top - 1];
            int e = stackIter[top - 1];
            if (e >= 0) {
                stackIter[top - 1] = nxt[e];
                int inEdge = stackEdge[top - 1];
                if (inEdge >= 0 && (e ^ 1) == inEdge) continue;
                int v = to[e];
                if (disc[v] < 0) {
                    disc[v] = low[v] = timer++;
                    stackNode[top] = v;
                    stackEdge[top] = e;
                    stackIter[top] = head[v];
                    top++;
                } else if (disc[v] < low[u]) {
                    low[u] = disc[v];
                }
            } else {
                top--;
                if (top > 0) {
                    int p = stackNode[top - 1];
                    if (low[u] < low[p]) low[p] = low[u];
                    if (low[u] > disc[p]) {
                        bridges.add(new int[] { Math.min(p, u), Math.max(p, u) });
                    }
                }
            }
        }
    }
    bridges.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    return bridges.toArray(new int[0][]);
}

C++

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<int> head(n, -1);
    int cap = max(1, (int) connections.size() * 2);
    vector<int> nxt(cap, -1), to(cap, 0);
    int ec = 0;
    for (auto& c : connections) {
        to[ec] = c[1]; nxt[ec] = head[c[0]]; head[c[0]] = ec; ec++;
        to[ec] = c[0]; nxt[ec] = head[c[1]]; head[c[1]] = ec; ec++;
    }
    vector<int> disc(n, -1), low(n, 0);
    int timer = 0;
    vector<vector<int>> bridges;
    vector<int> stackNode, stackEdge, stackIter;
    for (int s = 0; s < n; s++) {
        if (disc[s] >= 0) continue;
        disc[s] = low[s] = timer++;
        stackNode.push_back(s);
        stackEdge.push_back(-1);
        stackIter.push_back(head[s]);
        while (!stackNode.empty()) {
            int u = stackNode.back();
            int e = stackIter.back();
            if (e >= 0) {
                stackIter.back() = nxt[e];
                int inEdge = stackEdge.back();
                if (inEdge >= 0 && (e ^ 1) == inEdge) continue;
                int v = to[e];
                if (disc[v] < 0) {
                    disc[v] = low[v] = timer++;
                    stackNode.push_back(v);
                    stackEdge.push_back(e);
                    stackIter.push_back(head[v]);
                } else if (disc[v] < low[u]) {
                    low[u] = disc[v];
                }
            } else {
                stackNode.pop_back();
                stackEdge.pop_back();
                stackIter.pop_back();
                if (!stackNode.empty()) {
                    int p = stackNode.back();
                    if (low[u] < low[p]) low[p] = low[u];
                    if (low[u] > disc[p]) {
                        bridges.push_back({ min(p, u), max(p, u) });
                    }
                }
            }
        }
    }
    sort(bridges.begin(), bridges.end());
    return bridges;
}

JavaScript

var criticalConnections = function(n, connections) {
    var i;
    var head = [];
    for (i = 0; i < n; i++) head.push(-1);
    var cap = Math.max(1, connections.length * 2);
    var nxt = [], to = [];
    for (i = 0; i < cap; i++) { nxt.push(-1); to.push(0); }
    var ec = 0;
    for (i = 0; i < connections.length; i++) {
        var u0 = connections[i][0], v0 = connections[i][1];
        to[ec] = v0; nxt[ec] = head[u0]; head[u0] = ec; ec++;
        to[ec] = u0; nxt[ec] = head[v0]; head[v0] = ec; ec++;
    }
    var disc = [], low = [];
    for (i = 0; i < n; i++) { disc.push(-1); low.push(0); }
    var timer = 0;
    var bridges = [];
    var stackNode = [], stackEdge = [], stackIter = [];
    for (var s = 0; s < n; s++) {
        if (disc[s] >= 0) continue;
        disc[s] = low[s] = timer++;
        stackNode.push(s);
        stackEdge.push(-1);
        stackIter.push(head[s]);
        while (stackNode.length > 0) {
            var u = stackNode[stackNode.length - 1];
            var e = stackIter[stackIter.length - 1];
            if (e >= 0) {
                stackIter[stackIter.length - 1] = nxt[e];
                var inEdge = stackEdge[stackEdge.length - 1];
                if (inEdge >= 0 && (e ^ 1) === inEdge) continue;
                var v = to[e];
                if (disc[v] < 0) {
                    disc[v] = low[v] = timer++;
                    stackNode.push(v);
                    stackEdge.push(e);
                    stackIter.push(head[v]);
                } else if (disc[v] < low[u]) {
                    low[u] = disc[v];
                }
            } else {
                stackNode.pop();
                stackEdge.pop();
                stackIter.pop();
                if (stackNode.length > 0) {
                    var p = stackNode[stackNode.length - 1];
                    if (low[u] < low[p]) low[p] = low[u];
                    if (low[u] > disc[p]) {
                        bridges.push([Math.min(p, u), Math.max(p, u)]);
                    }
                }
            }
        }
    }
    bridges.sort(function(x, y) { return (x[0] - y[0]) || (x[1] - y[1]); });
    return bridges;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Graph Data Structure