#92 · Advanced Graphs

Critical Connections in a Network

There are n servers numbered 0 … n − 1 connected by undirected connections forming a connected network. A critical connection (bridge) is one whose removal makes some servers unable to reach others. Return all critical connections in any order.

HardLeetCode

Current
On path / queued
Done
Cycle / blocked

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Adjacency lists and the DFS tree

A depth-first search from node 0 classifies every edge as a tree edge (to a new node) or a back edge (to an already-visited ancestor). Every non-tree edge closes exactly one cycle; tree edges not covered by any cycle are bridges.

Memory layout

Arrays indexed by node: discovery time, low-link, parent; adjacency lists of size 2E.

Operation	Cost
DFS	O(V + E)

Discovery time and low-link values

disc[v] is when DFS first visited v. low[v] is the smallest disc reachable from v's DFS subtree using tree edges and at most one back edge. A tree edge parent→child is a bridge iff low[child] > disc[parent].

Memory layout

Two integer arrays of size n and a timer.

Operation	Cost
update	O(1) per edge

Flat edge arrays with twin slots

For iterative DFS and parallel-edge safety, store each undirected connection as two slots 2k and 2k + 1 (e ^ 1 is the twin). Skipping the twin of the entry edge (not "the parent node") treats parallel edges correctly.

Memory layout

Arrays head[n], nextEdge[2E], to[2E]; no per-node lists.

Operation	Cost
iterate neighbours	O(deg)

Why it fits

An edge is a bridge exactly when no cycle contains it, and DFS exposes cycles as back edges, so one traversal can answer for all edges.
Low-link turns "does any back edge cover this tree edge?" into one integer comparison, avoiding any explicit cycle walking.
The method is the same used for articulation points and strongly connected components (Tarjan), so it is a core graph technique.

Why alternatives degrade

Union-find:: It detects that an edge closes a cycle while adding edges, but cannot tell which earlier edges became non-bridges.
BFS / shortest paths:: Distances do not reveal bridges; you would need to remove every edge and re-check connectivity.
Removing every edge and re-running a search:: Correct but O(E · (V + E)); the low-link method does all edges in one pass.

Four approaches, from naive to production

1 · beginner

Remove each edge, test connectivity

time O(E · (V + E))space O(V + E)

For every connection, build the graph without it and search from node 0. If fewer than n nodes are reached the edge is critical.

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<vector<int>> result;
    auto connected = [&](int skip) -> bool {
        vector<vector<int>> adj(n);
        for (int i = 0; i < (int)connections.size(); i++) {
            if (i == skip) continue;
            adj[connections[i][0]].push_back(connections[i][1]);
            adj[connections[i][1]].push_back(connections[i][0]);
        }
        vector<bool> seen(n, false);
        vector<int> stack{0};
        seen[0] = true;
        int count = 1;
        while (!stack.empty()) {
            int node = stack.back(); stack.pop_back();
            for (int next : adj[node]) {
                if (!seen[next]) { seen[next] = true; count++; stack.push_back(next); }
            }
        }
        return count == n;
    };
    for (int i = 0; i < (int)connections.size(); i++) {
        if (!connected(i)) result.push_back(connections[i]);
    }
    return result;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < connections.size(); i++) {
        if (!connected(n, connections, i)) result.add(connections.get(i));
    }
    return result;
}
private boolean connected(int n, List<List<Integer>> connections, int skip) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
    for (int i = 0; i < connections.size(); i++) {
        if (i == skip) continue;
        adj.get(connections.get(i).get(0)).add(connections.get(i).get(1));
        adj.get(connections.get(i).get(1)).add(connections.get(i).get(0));
    }
    boolean[] seen = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>(); stack.push(0);
    seen[0] = true;
    int count = 1;
    while (!stack.isEmpty()) {
        int node = stack.pop();
        for (int next : adj.get(node)) {
            if (!seen[next]) { seen[next] = true; count++; stack.push(next); }
        }
    }
    return count == n;
}

def critical_connections(n, connections):
    result = []
    def connected(skip):
        adj = [[] for _ in range(n)]
        for i, (a, b) in enumerate(connections):
            if i == skip: continue
            adj[a].append(b)
            adj[b].append(a)
        seen = [False] * n
        stack = [0]
        seen[0] = True
        count = 1
        while stack:
            node = stack.pop()
            for nxt in adj[node]:
                if not seen[nxt]:
                    seen[nxt] = True; count += 1; stack.append(nxt)
        return count == n
    for i, edge in enumerate(connections):
        if not connected(i): result.append(edge)
    return result

function criticalConnections(n: number, connections: number[][]): number[][] {
  const result: number[][] = [];
  const connected = (skip: number): boolean => {
    const adj: number[][] = Array.from({ length: n }, () => []);
    connections.forEach(([a, b], i) => {
      if (i === skip) return;
      adj[a].push(b);
      adj[b].push(a);
    });
    const seen = new Array<boolean>(n).fill(false);
    const stack = [0];
    seen[0] = true;
    let count = 1;
    while (stack.length > 0) {
      const node = stack.pop()!;
      for (const next of adj[node]) {
        if (!seen[next]) { seen[next] = true; count++; stack.push(next); }
      }
    }
    return count === n;
  };
  connections.forEach((edge, i) => {
    if (!connected(i)) result.push(edge);
  });
  return result;
}

Flaws & bottlenecks

Rebuilds the adjacency lists for every edge.
Quadratic: 10⁵ edges means 10¹⁰ steps.
Does no shared work between the E searches.

Interviewer cross-questions

Why start the search at node 0?

Say: The network is connected, so after removing a bridge node 0 reaches only its own side; the count shows how many nodes are cut off.

Is this correct for graphs that are not connected?

Say: Not as written: it assumes connectivity. You would compare the number of components before and after instead.

How can all edges be checked in one pass?

Say: Use DFS discovery times and low-link values (Tarjan's bridge algorithm).

2 · intermediate

DFS tree and cycle marking

time O(V · E) worst casespace O(V + E)

Run one DFS and record parent pointers and depths. For each back edge (to a shallower node) mark the edge and all tree edges up to that ancestor as lying on a cycle. Unmarked edges are bridges.

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < (int)connections.size(); i++) {
        adj[connections[i][0]].push_back({connections[i][1], i});
        adj[connections[i][1]].push_back({connections[i][0], i});
    }
    vector<int> depth(n, -1);
    vector<int> parent(n, -1);
    vector<int> parentEdge(n, -1);
    vector<bool> onCycle(connections.size(), false);
    function<void(int)> dfs = [&](int node) {
        for (auto [next, id] : adj[node]) {
            if (id == parentEdge[node]) continue;
            if (depth[next] == -1) {
                depth[next] = depth[node] + 1;
                parent[next] = node;
                parentEdge[next] = id;
                dfs(next);
            } else if (depth[next] < depth[node]) {
                onCycle[id] = true;
                for (int v = node; v != next; v = parent[v]) onCycle[parentEdge[v]] = true;
            }
        }
    };
    depth[0] = 0;
    dfs(0);
    vector<vector<int>> result;
    for (int id = 0; id < (int)connections.size(); id++) if (!onCycle[id]) result.push_back(connections[id]);
    return result;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
    for (int i = 0; i < connections.size(); i++) {
        adj.get(connections.get(i).get(0)).add(new int[]{connections.get(i).get(1), i});
        adj.get(connections.get(i).get(1)).add(new int[]{connections.get(i).get(0), i});
    }
    int[] depth = new int[n]; Arrays.fill(depth, -1);
    int[] parent = new int[n]; Arrays.fill(parent, -1);
    int[] parentEdge = new int[n]; Arrays.fill(parentEdge, -1);
    boolean[] onCycle = new boolean[connections.size()];
    depth[0] = 0;
    dfs(0, adj, depth, parent, parentEdge, onCycle);
    List<List<Integer>> result = new ArrayList<>();
    for (int id = 0; id < connections.size(); id++) if (!onCycle[id]) result.add(connections.get(id));
    return result;
}
private void dfs(int node, List<List<int[]>> adj, int[] depth, int[] parent, int[] parentEdge, boolean[] onCycle) {
    for (int[] e : adj.get(node)) {
        int next = e[0], id = e[1];
        if (id == parentEdge[node]) continue;
        if (depth[next] == -1) {
            depth[next] = depth[node] + 1;
            parent[next] = node;
            parentEdge[next] = id;
            dfs(next, adj, depth, parent, parentEdge, onCycle);
        } else if (depth[next] < depth[node]) {
            onCycle[id] = true;
            for (int v = node; v != next; v = parent[v]) onCycle[parentEdge[v]] = true;
        }
    }
}

def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for i, (a, b) in enumerate(connections):
        adj[a].append((b, i)); adj[b].append((a, i))
    depth = [-1] * n
    parent = [-1] * n
    parent_edge = [-1] * n
    on_cycle = [False] * len(connections)
    def dfs(node):
        for nxt, eid in adj[node]:
            if eid == parent_edge[node]: continue
            if depth[nxt] == -1:
                depth[nxt] = depth[node] + 1
                parent[nxt] = node
                parent_edge[nxt] = eid
                dfs(nxt)
            elif depth[nxt] < depth[node]:
                on_cycle[eid] = True
                v = node
                while v != nxt:
                    on_cycle[parent_edge[v]] = True; v = parent[v]
    depth[0] = 0
    dfs(0)
    return [c for i, c in enumerate(connections) if not on_cycle[i]]

function criticalConnections(n: number, connections: number[][]): number[][] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  connections.forEach(([a, b], i) => { adj[a].push([b, i]); adj[b].push([a, i]); });
  const depth = new Array<number>(n).fill(-1);
  const parent = new Array<number>(n).fill(-1);
  const parentEdge = new Array<number>(n).fill(-1);
  const onCycle = new Array<boolean>(connections.length).fill(false);
  const dfs = (node: number): void => {
    for (const [next, id] of adj[node]) {
      if (id === parentEdge[node]) continue;
      if (depth[next] === -1) {
        depth[next] = depth[node] + 1;
        parent[next] = node;
        parentEdge[next] = id;
        dfs(next);
      } else if (depth[next] < depth[node]) {
        onCycle[id] = true;
        for (let v = node; v !== next; v = parent[v]) onCycle[parentEdge[v]] = true;
      }
    }
  };
  depth[0] = 0;
  dfs(0);
  return connections.filter((_, id) => !onCycle[id]);
}

Flaws & bottlenecks

Each back edge may walk up O(V) tree edges.
Re-marks tree edges that were already on a cycle.
Needs parent and parent-edge arrays on top of depth.

Interviewer cross-questions

Why identify edges by id and not by node?

Say: To tell the entry edge from a parallel edge to the same parent, which would be a genuine cycle.

How could the walk be avoided?

Say: Instead of marking the path, propagate the minimum reachable depth upward: that is exactly low-link.

Can a tree edge be a bridge and have a back edge below it?

Say: Only if no back edge from its subtree reaches the parent or above; otherwise it is on a cycle.

3 · advanced

Tarjan's bridge algorithm

time O(V + E)space O(V + E)

One DFS computing disc[v] and low[v]. After returning from a child, low[node] = min(low[node], low[child]); the tree edge is a bridge if low[child] > disc[node]. Back edges update low[node] with disc[next].

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<vector<int>> adj(n);
    for (auto& c : connections) { adj[c[0]].push_back(c[1]); adj[c[1]].push_back(c[0]); }
    vector<int> disc(n, -1);
    vector<int> low(n, 0);
    vector<vector<int>> bridges;
    int timer = 0;
    function<void(int, int)> dfs = [&](int node, int parent) {
        disc[node] = low[node] = timer++;
        for (int next : adj[node]) {
            if (next == parent) continue;
            if (disc[next] == -1) {
                dfs(next, node);
                low[node] = min(low[node], low[next]);
                if (low[next] > disc[node]) bridges.push_back({node, next});
            } else {
                low[node] = min(low[node], disc[next]);
            }
        }
    };
    dfs(0, -1);
    return bridges;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
    for (List<Integer> c : connections) { adj.get(c.get(0)).add(c.get(1)); adj.get(c.get(1)).add(c.get(0)); }
    int[] disc = new int[n]; Arrays.fill(disc, -1);
    int[] low = new int[n];
    List<List<Integer>> bridges = new ArrayList<>();
    int[] timer = {0};
    dfs(0, -1, adj, disc, low, timer, bridges);
    return bridges;
}
private void dfs(int node, int parent, List<List<Integer>> adj, int[] disc, int[] low, int[] timer, List<List<Integer>> bridges) {
    disc[node] = low[node] = timer[0]++;
    for (int next : adj.get(node)) {
        if (next == parent) continue;
        if (disc[next] == -1) {
            dfs(next, node, adj, disc, low, timer, bridges);
            low[node] = Math.min(low[node], low[next]);
            if (low[next] > disc[node]) bridges.add(Arrays.asList(node, next));
        } else {
            low[node] = Math.min(low[node], disc[next]);
        }
    }
}

def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for a, b in connections:
        adj[a].append(b); adj[b].append(a)
    disc = [-1] * n
    low = [0] * n
    bridges = []
    timer = 0
    def dfs(node, parent):
        nonlocal timer
        disc[node] = low[node] = timer; timer += 1
        for nxt in adj[node]:
            if nxt == parent: continue
            if disc[nxt] == -1:
                dfs(nxt, node)
                low[node] = min(low[node], low[nxt])
                if low[nxt] > disc[node]: bridges.append([node, nxt])
            else:
                low[node] = min(low[node], disc[nxt])
    dfs(0, -1)
    return bridges

function criticalConnections(n: number, connections: number[][]): number[][] {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of connections) { adj[a].push(b); adj[b].push(a); }
  const disc = new Array<number>(n).fill(-1);
  const low = new Array<number>(n).fill(0);
  const bridges: number[][] = [];
  let timer = 0;
  const dfs = (node: number, parent: number): void => {
    disc[node] = low[node] = timer++;
    for (const next of adj[node]) {
      if (next === parent) continue;
      if (disc[next] === -1) {
        dfs(next, node);
        low[node] = Math.min(low[node], low[next]);
        if (low[next] > disc[node]) bridges.push([node, next]);
      } else {
        low[node] = Math.min(low[node], disc[next]);
      }
    }
  };
  dfs(0, -1);
  return bridges;
}

Flaws & bottlenecks

Recursion depth can reach V, overflowing the call stack for long chains.
Skipping "next === parent" is wrong with parallel edges.
The low-link idea takes practice to explain precisely.

Interviewer cross-questions

Why ">" and not ">="?

Say: low[child] = disc[parent] means the child can reach the parent itself via a back edge, so the tree edge is on a cycle. A bridge needs the child to be unable to reach the parent at all.

Why skip the parent?

Say: The edge back to the parent is the tree edge we came through; counting it as a back edge would make every edge look like part of a cycle.

How does this differ for articulation points?

Say: There the condition is low[child] ≥ disc[parent], because a cut node only needs the child subtree to be unable to bypass it.

4 · expert

Iterative Tarjan with edge slots

time O(V + E)space O(V + E)

Store the graph in flat arrays with twin edge slots, keep an explicit stack of nodes and entry edges, and replace the recursion with a cursor per node. Skip only the twin of the entry edge so parallel edges are handled. Loop over roots for disconnected input.

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<int> head(n, -1);
    vector<int> nextEdge;
    vector<int> to;
    auto addEdge = [&](int a, int b) { to.push_back(b); nextEdge.push_back(head[a]); head[a] = (int)to.size() - 1; };
    for (auto& c : connections) { addEdge(c[0], c[1]); addEdge(c[1], c[0]); }
    vector<int> disc(n, -1);
    vector<int> low(n, 0);
    vector<int> cursor(head);
    vector<int> stackNode;
    vector<int> stackEdge;
    vector<vector<int>> bridges;
    int timer = 0;
    for (int root = 0; root < n; root++) {
        if (disc[root] != -1) continue;
        disc[root] = low[root] = timer++;
        stackNode.push_back(root);
        stackEdge.push_back(-1);
        while (!stackNode.empty()) {
            int node = stackNode.back();
            int e = cursor[node];
            if (e != -1) {
                cursor[node] = nextEdge[e];
                if ((e ^ 1) == stackEdge.back()) continue;
                int next = to[e];
                if (disc[next] == -1) {
                    disc[next] = low[next] = timer++;
                    stackNode.push_back(next);
                    stackEdge.push_back(e);
                } else {
                    low[node] = min(low[node], disc[next]);
                }
            } else {
                stackNode.pop_back();
                stackEdge.pop_back();
                if (!stackNode.empty()) {
                    int parent = stackNode.back();
                    low[parent] = min(low[parent], low[node]);
                    if (low[node] > disc[parent]) bridges.push_back({parent, node});
                }
            }
        }
    }
    return bridges;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    int[] head = new int[n]; Arrays.fill(head, -1);
    int m = connections.size() * 2;
    int[] nextEdge = new int[m];
    int[] to = new int[m];
    int size = 0;
    for (List<Integer> c : connections) {
        int a = c.get(0), b = c.get(1);
        to[size] = b; nextEdge[size] = head[a]; head[a] = size++;
        to[size] = a; nextEdge[size] = head[b]; head[b] = size++;
    }
    int[] disc = new int[n]; Arrays.fill(disc, -1);
    int[] low = new int[n];
    int[] cursor = head.clone();
    int[] stackNode = new int[n + 1]; int top = 0;
    int[] stackEdge = new int[n + 1];
    List<List<Integer>> bridges = new ArrayList<>();
    int timer = 0;
    for (int root = 0; root < n; root++) {
        if (disc[root] != -1) continue;
        disc[root] = low[root] = timer++;
        stackNode[top] = root;
        stackEdge[top++] = -1;
        while (top > 0) {
            int node = stackNode[top - 1];
            int e = cursor[node];
            if (e != -1) {
                cursor[node] = nextEdge[e];
                if ((e ^ 1) == stackEdge[top - 1]) continue;
                int next = to[e];
                if (disc[next] == -1) {
                    disc[next] = low[next] = timer++;
                    stackNode[top] = next;
                    stackEdge[top++] = e;
                } else {
                    low[node] = Math.min(low[node], disc[next]);
                }
            } else {
                top--;
                if (top > 0) {
                    int parent = stackNode[top - 1];
                    low[parent] = Math.min(low[parent], low[node]);
                    if (low[node] > disc[parent]) bridges.add(Arrays.asList(parent, node));
                }
            }
        }
    }
    return bridges;
}

def critical_connections(n, connections):
    head = [-1] * n
    next_edge = []
    to = []
    def add_edge(a, b):
        to.append(b); next_edge.append(head[a]); head[a] = len(to) - 1
    for a, b in connections:
        add_edge(a, b); add_edge(b, a)
    disc = [-1] * n
    low = [0] * n
    cursor = head[:]
    stack_node = []
    stack_edge = []
    bridges = []
    timer = 0
    for root in range(n):
        if disc[root] != -1: continue
        disc[root] = low[root] = timer; timer += 1
        stack_node.append(root)
        stack_edge.append(-1)
        while stack_node:
            node = stack_node[-1]
            e = cursor[node]
            if e != -1:
                cursor[node] = next_edge[e]
                if (e ^ 1) == stack_edge[-1]: continue
                nxt = to[e]
                if disc[nxt] == -1:
                    disc[nxt] = low[nxt] = timer; timer += 1
                    stack_node.append(nxt)
                    stack_edge.append(e)
                else:
                    low[node] = min(low[node], disc[nxt])
            else:
                stack_node.pop()
                stack_edge.pop()
                if stack_node:
                    parent = stack_node[-1]
                    low[parent] = min(low[parent], low[node])
                    if low[node] > disc[parent]: bridges.append([parent, node])
    return bridges

function criticalConnections(n: number, connections: number[][]): number[][] {
  const head = new Array<number>(n).fill(-1);
  const nextEdge: number[] = [];
  const to: number[] = [];
  const addEdge = (a: number, b: number): void => { to.push(b); nextEdge.push(head[a]); head[a] = to.length - 1; };
  connections.forEach(([a, b]) => { addEdge(a, b); addEdge(b, a); });
  const disc = new Array<number>(n).fill(-1);
  const low = new Array<number>(n).fill(0);
  const cursor = head.slice();
  const stackNode: number[] = [];
  const stackEdge: number[] = [];
  const bridges: number[][] = [];
  let timer = 0;
  for (let root = 0; root < n; root++) {
    if (disc[root] !== -1) continue;
    disc[root] = low[root] = timer++;
    stackNode.push(root);
    stackEdge.push(-1);
    while (stackNode.length > 0) {
      const node = stackNode[stackNode.length - 1];
      const e = cursor[node];
      if (e !== -1) {
        cursor[node] = nextEdge[e];
        if ((e ^ 1) === stackEdge[stackEdge.length - 1]) continue;
        const next = to[e];
        if (disc[next] === -1) {
          disc[next] = low[next] = timer++;
          stackNode.push(next);
          stackEdge.push(e);
        } else {
          low[node] = Math.min(low[node], disc[next]);
        }
      } else {
        stackNode.pop();
        stackEdge.pop();
        if (stackNode.length > 0) {
          const parent = stackNode[stackNode.length - 1];
          low[parent] = Math.min(low[parent], low[node]);
          if (low[node] > disc[parent]) bridges.push([parent, node]);
        }
      }
    }
  }
  return bridges;
}

Flaws & bottlenecks

Much more code than the recursive version.
Order of neighbours is reversed by head insertion (irrelevant for the answer).
Bugs are easy: forgetting the twin trick, or updating low after popping.

Interviewer cross-questions

Why is this needed in production?

Say: A network can be a 10⁵-node chain; recursion that deep overflows the stack in most runtimes. An explicit stack has no such limit.

Why skip by edge id and not by parent node?

Say: Two parallel connections between the same servers form a cycle, so neither is critical; skipping only the entry edge (via e ^ 1) keeps the second one as a back edge.

What about disconnected input?

Say: The outer loop restarts from every unvisited root; bridges are still found per component (the problem guarantees connectivity, but robust code does not assume it).

Synchronized code walkthrough

Showing: Remove each edge, test connectivity — shares the player above; click any step to jump.

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<vector<int>> result;
    auto connected = [&](int skip) -> bool {
        vector<vector<int>> adj(n);
        for (int i = 0; i < (int)connections.size(); i++) {
            if (i == skip) continue;
            adj[connections[i][0]].push_back(connections[i][1]);
            adj[connections[i][1]].push_back(connections[i][0]);
        }
        vector<bool> seen(n, false);
        vector<int> stack{0};
        seen[0] = true;
        int count = 1;
        while (!stack.empty()) {
            int node = stack.back(); stack.pop_back();
            for (int next : adj[node]) {
                if (!seen[next]) { seen[next] = true; count++; stack.push_back(next); }
            }
        }
        return count == n;
    };
    for (int i = 0; i < (int)connections.size(); i++) {
        if (!connected(i)) result.push_back(connections[i]);
    }
    return result;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < connections.size(); i++) {
        if (!connected(n, connections, i)) result.add(connections.get(i));
    }
    return result;
}
private boolean connected(int n, List<List<Integer>> connections, int skip) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
    for (int i = 0; i < connections.size(); i++) {
        if (i == skip) continue;
        adj.get(connections.get(i).get(0)).add(connections.get(i).get(1));
        adj.get(connections.get(i).get(1)).add(connections.get(i).get(0));
    }
    boolean[] seen = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>(); stack.push(0);
    seen[0] = true;
    int count = 1;
    while (!stack.isEmpty()) {
        int node = stack.pop();
        for (int next : adj.get(node)) {
            if (!seen[next]) { seen[next] = true; count++; stack.push(next); }
        }
    }
    return count == n;
}

def critical_connections(n, connections):
    result = []
    def connected(skip):
        adj = [[] for _ in range(n)]
        for i, (a, b) in enumerate(connections):
            if i == skip: continue
            adj[a].append(b)
            adj[b].append(a)
        seen = [False] * n
        stack = [0]
        seen[0] = True
        count = 1
        while stack:
            node = stack.pop()
            for nxt in adj[node]:
                if not seen[nxt]:
                    seen[nxt] = True; count += 1; stack.append(nxt)
        return count == n
    for i, edge in enumerate(connections):
        if not connected(i): result.append(edge)
    return result

function criticalConnections(n: number, connections: number[][]): number[][] {
  const result: number[][] = [];
  const connected = (skip: number): boolean => {
    const adj: number[][] = Array.from({ length: n }, () => []);
    connections.forEach(([a, b], i) => {
      if (i === skip) return;
      adj[a].push(b);
      adj[b].push(a);
    });
    const seen = new Array<boolean>(n).fill(false);
    const stack = [0];
    seen[0] = true;
    let count = 1;
    while (stack.length > 0) {
      const node = stack.pop()!;
      for (const next of adj[node]) {
        if (!seen[next]) { seen[next] = true; count++; stack.push(next); }
      }
    }
    return count === n;
  };
  connections.forEach((edge, i) => {
    if (!connected(i)) result.push(edge);
  });
  return result;
}

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < (int)connections.size(); i++) {
        adj[connections[i][0]].push_back({connections[i][1], i});
        adj[connections[i][1]].push_back({connections[i][0], i});
    }
    vector<int> depth(n, -1);
    vector<int> parent(n, -1);
    vector<int> parentEdge(n, -1);
    vector<bool> onCycle(connections.size(), false);
    function<void(int)> dfs = [&](int node) {
        for (auto [next, id] : adj[node]) {
            if (id == parentEdge[node]) continue;
            if (depth[next] == -1) {
                depth[next] = depth[node] + 1;
                parent[next] = node;
                parentEdge[next] = id;
                dfs(next);
            } else if (depth[next] < depth[node]) {
                onCycle[id] = true;
                for (int v = node; v != next; v = parent[v]) onCycle[parentEdge[v]] = true;
            }
        }
    };
    depth[0] = 0;
    dfs(0);
    vector<vector<int>> result;
    for (int id = 0; id < (int)connections.size(); id++) if (!onCycle[id]) result.push_back(connections[id]);
    return result;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
    for (int i = 0; i < connections.size(); i++) {
        adj.get(connections.get(i).get(0)).add(new int[]{connections.get(i).get(1), i});
        adj.get(connections.get(i).get(1)).add(new int[]{connections.get(i).get(0), i});
    }
    int[] depth = new int[n]; Arrays.fill(depth, -1);
    int[] parent = new int[n]; Arrays.fill(parent, -1);
    int[] parentEdge = new int[n]; Arrays.fill(parentEdge, -1);
    boolean[] onCycle = new boolean[connections.size()];
    depth[0] = 0;
    dfs(0, adj, depth, parent, parentEdge, onCycle);
    List<List<Integer>> result = new ArrayList<>();
    for (int id = 0; id < connections.size(); id++) if (!onCycle[id]) result.add(connections.get(id));
    return result;
}
private void dfs(int node, List<List<int[]>> adj, int[] depth, int[] parent, int[] parentEdge, boolean[] onCycle) {
    for (int[] e : adj.get(node)) {
        int next = e[0], id = e[1];
        if (id == parentEdge[node]) continue;
        if (depth[next] == -1) {
            depth[next] = depth[node] + 1;
            parent[next] = node;
            parentEdge[next] = id;
            dfs(next, adj, depth, parent, parentEdge, onCycle);
        } else if (depth[next] < depth[node]) {
            onCycle[id] = true;
            for (int v = node; v != next; v = parent[v]) onCycle[parentEdge[v]] = true;
        }
    }
}

def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for i, (a, b) in enumerate(connections):
        adj[a].append((b, i)); adj[b].append((a, i))
    depth = [-1] * n
    parent = [-1] * n
    parent_edge = [-1] * n
    on_cycle = [False] * len(connections)
    def dfs(node):
        for nxt, eid in adj[node]:
            if eid == parent_edge[node]: continue
            if depth[nxt] == -1:
                depth[nxt] = depth[node] + 1
                parent[nxt] = node
                parent_edge[nxt] = eid
                dfs(nxt)
            elif depth[nxt] < depth[node]:
                on_cycle[eid] = True
                v = node
                while v != nxt:
                    on_cycle[parent_edge[v]] = True; v = parent[v]
    depth[0] = 0
    dfs(0)
    return [c for i, c in enumerate(connections) if not on_cycle[i]]

function criticalConnections(n: number, connections: number[][]): number[][] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  connections.forEach(([a, b], i) => { adj[a].push([b, i]); adj[b].push([a, i]); });
  const depth = new Array<number>(n).fill(-1);
  const parent = new Array<number>(n).fill(-1);
  const parentEdge = new Array<number>(n).fill(-1);
  const onCycle = new Array<boolean>(connections.length).fill(false);
  const dfs = (node: number): void => {
    for (const [next, id] of adj[node]) {
      if (id === parentEdge[node]) continue;
      if (depth[next] === -1) {
        depth[next] = depth[node] + 1;
        parent[next] = node;
        parentEdge[next] = id;
        dfs(next);
      } else if (depth[next] < depth[node]) {
        onCycle[id] = true;
        for (let v = node; v !== next; v = parent[v]) onCycle[parentEdge[v]] = true;
      }
    }
  };
  depth[0] = 0;
  dfs(0);
  return connections.filter((_, id) => !onCycle[id]);
}

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<vector<int>> adj(n);
    for (auto& c : connections) { adj[c[0]].push_back(c[1]); adj[c[1]].push_back(c[0]); }
    vector<int> disc(n, -1);
    vector<int> low(n, 0);
    vector<vector<int>> bridges;
    int timer = 0;
    function<void(int, int)> dfs = [&](int node, int parent) {
        disc[node] = low[node] = timer++;
        for (int next : adj[node]) {
            if (next == parent) continue;
            if (disc[next] == -1) {
                dfs(next, node);
                low[node] = min(low[node], low[next]);
                if (low[next] > disc[node]) bridges.push_back({node, next});
            } else {
                low[node] = min(low[node], disc[next]);
            }
        }
    };
    dfs(0, -1);
    return bridges;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
    for (List<Integer> c : connections) { adj.get(c.get(0)).add(c.get(1)); adj.get(c.get(1)).add(c.get(0)); }
    int[] disc = new int[n]; Arrays.fill(disc, -1);
    int[] low = new int[n];
    List<List<Integer>> bridges = new ArrayList<>();
    int[] timer = {0};
    dfs(0, -1, adj, disc, low, timer, bridges);
    return bridges;
}
private void dfs(int node, int parent, List<List<Integer>> adj, int[] disc, int[] low, int[] timer, List<List<Integer>> bridges) {
    disc[node] = low[node] = timer[0]++;
    for (int next : adj.get(node)) {
        if (next == parent) continue;
        if (disc[next] == -1) {
            dfs(next, node, adj, disc, low, timer, bridges);
            low[node] = Math.min(low[node], low[next]);
            if (low[next] > disc[node]) bridges.add(Arrays.asList(node, next));
        } else {
            low[node] = Math.min(low[node], disc[next]);
        }
    }
}

def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for a, b in connections:
        adj[a].append(b); adj[b].append(a)
    disc = [-1] * n
    low = [0] * n
    bridges = []
    timer = 0
    def dfs(node, parent):
        nonlocal timer
        disc[node] = low[node] = timer; timer += 1
        for nxt in adj[node]:
            if nxt == parent: continue
            if disc[nxt] == -1:
                dfs(nxt, node)
                low[node] = min(low[node], low[nxt])
                if low[nxt] > disc[node]: bridges.append([node, nxt])
            else:
                low[node] = min(low[node], disc[nxt])
    dfs(0, -1)
    return bridges

function criticalConnections(n: number, connections: number[][]): number[][] {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of connections) { adj[a].push(b); adj[b].push(a); }
  const disc = new Array<number>(n).fill(-1);
  const low = new Array<number>(n).fill(0);
  const bridges: number[][] = [];
  let timer = 0;
  const dfs = (node: number, parent: number): void => {
    disc[node] = low[node] = timer++;
    for (const next of adj[node]) {
      if (next === parent) continue;
      if (disc[next] === -1) {
        dfs(next, node);
        low[node] = Math.min(low[node], low[next]);
        if (low[next] > disc[node]) bridges.push([node, next]);
      } else {
        low[node] = Math.min(low[node], disc[next]);
      }
    }
  };
  dfs(0, -1);
  return bridges;
}

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<int> head(n, -1);
    vector<int> nextEdge;
    vector<int> to;
    auto addEdge = [&](int a, int b) { to.push_back(b); nextEdge.push_back(head[a]); head[a] = (int)to.size() - 1; };
    for (auto& c : connections) { addEdge(c[0], c[1]); addEdge(c[1], c[0]); }
    vector<int> disc(n, -1);
    vector<int> low(n, 0);
    vector<int> cursor(head);
    vector<int> stackNode;
    vector<int> stackEdge;
    vector<vector<int>> bridges;
    int timer = 0;
    for (int root = 0; root < n; root++) {
        if (disc[root] != -1) continue;
        disc[root] = low[root] = timer++;
        stackNode.push_back(root);
        stackEdge.push_back(-1);
        while (!stackNode.empty()) {
            int node = stackNode.back();
            int e = cursor[node];
            if (e != -1) {
                cursor[node] = nextEdge[e];
                if ((e ^ 1) == stackEdge.back()) continue;
                int next = to[e];
                if (disc[next] == -1) {
                    disc[next] = low[next] = timer++;
                    stackNode.push_back(next);
                    stackEdge.push_back(e);
                } else {
                    low[node] = min(low[node], disc[next]);
                }
            } else {
                stackNode.pop_back();
                stackEdge.pop_back();
                if (!stackNode.empty()) {
                    int parent = stackNode.back();
                    low[parent] = min(low[parent], low[node]);
                    if (low[node] > disc[parent]) bridges.push_back({parent, node});
                }
            }
        }
    }
    return bridges;
}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    int[] head = new int[n]; Arrays.fill(head, -1);
    int m = connections.size() * 2;
    int[] nextEdge = new int[m];
    int[] to = new int[m];
    int size = 0;
    for (List<Integer> c : connections) {
        int a = c.get(0), b = c.get(1);
        to[size] = b; nextEdge[size] = head[a]; head[a] = size++;
        to[size] = a; nextEdge[size] = head[b]; head[b] = size++;
    }
    int[] disc = new int[n]; Arrays.fill(disc, -1);
    int[] low = new int[n];
    int[] cursor = head.clone();
    int[] stackNode = new int[n + 1]; int top = 0;
    int[] stackEdge = new int[n + 1];
    List<List<Integer>> bridges = new ArrayList<>();
    int timer = 0;
    for (int root = 0; root < n; root++) {
        if (disc[root] != -1) continue;
        disc[root] = low[root] = timer++;
        stackNode[top] = root;
        stackEdge[top++] = -1;
        while (top > 0) {
            int node = stackNode[top - 1];
            int e = cursor[node];
            if (e != -1) {
                cursor[node] = nextEdge[e];
                if ((e ^ 1) == stackEdge[top - 1]) continue;
                int next = to[e];
                if (disc[next] == -1) {
                    disc[next] = low[next] = timer++;
                    stackNode[top] = next;
                    stackEdge[top++] = e;
                } else {
                    low[node] = Math.min(low[node], disc[next]);
                }
            } else {
                top--;
                if (top > 0) {
                    int parent = stackNode[top - 1];
                    low[parent] = Math.min(low[parent], low[node]);
                    if (low[node] > disc[parent]) bridges.add(Arrays.asList(parent, node));
                }
            }
        }
    }
    return bridges;
}

def critical_connections(n, connections):
    head = [-1] * n
    next_edge = []
    to = []
    def add_edge(a, b):
        to.append(b); next_edge.append(head[a]); head[a] = len(to) - 1
    for a, b in connections:
        add_edge(a, b); add_edge(b, a)
    disc = [-1] * n
    low = [0] * n
    cursor = head[:]
    stack_node = []
    stack_edge = []
    bridges = []
    timer = 0
    for root in range(n):
        if disc[root] != -1: continue
        disc[root] = low[root] = timer; timer += 1
        stack_node.append(root)
        stack_edge.append(-1)
        while stack_node:
            node = stack_node[-1]
            e = cursor[node]
            if e != -1:
                cursor[node] = next_edge[e]
                if (e ^ 1) == stack_edge[-1]: continue
                nxt = to[e]
                if disc[nxt] == -1:
                    disc[nxt] = low[nxt] = timer; timer += 1
                    stack_node.append(nxt)
                    stack_edge.append(e)
                else:
                    low[node] = min(low[node], disc[nxt])
            else:
                stack_node.pop()
                stack_edge.pop()
                if stack_node:
                    parent = stack_node[-1]
                    low[parent] = min(low[parent], low[node])
                    if low[node] > disc[parent]: bridges.append([parent, node])
    return bridges

function criticalConnections(n: number, connections: number[][]): number[][] {
  const head = new Array<number>(n).fill(-1);
  const nextEdge: number[] = [];
  const to: number[] = [];
  const addEdge = (a: number, b: number): void => { to.push(b); nextEdge.push(head[a]); head[a] = to.length - 1; };
  connections.forEach(([a, b]) => { addEdge(a, b); addEdge(b, a); });
  const disc = new Array<number>(n).fill(-1);
  const low = new Array<number>(n).fill(0);
  const cursor = head.slice();
  const stackNode: number[] = [];
  const stackEdge: number[] = [];
  const bridges: number[][] = [];
  let timer = 0;
  for (let root = 0; root < n; root++) {
    if (disc[root] !== -1) continue;
    disc[root] = low[root] = timer++;
    stackNode.push(root);
    stackEdge.push(-1);
    while (stackNode.length > 0) {
      const node = stackNode[stackNode.length - 1];
      const e = cursor[node];
      if (e !== -1) {
        cursor[node] = nextEdge[e];
        if ((e ^ 1) === stackEdge[stackEdge.length - 1]) continue;
        const next = to[e];
        if (disc[next] === -1) {
          disc[next] = low[next] = timer++;
          stackNode.push(next);
          stackEdge.push(e);
        } else {
          low[node] = Math.min(low[node], disc[next]);
        }
      } else {
        stackNode.pop();
        stackEdge.pop();
        if (stackNode.length > 0) {
          const parent = stackNode[stackNode.length - 1];
          low[parent] = Math.min(low[parent], low[node]);
          if (low[node] > disc[parent]) bridges.push([parent, node]);
        }
      }
    }
  }
  return bridges;
}