hard Critical Connections in a Network

Problem Statement

You are given n servers numbered from 0 to n-1, connected by some number of undirected connections where connections[i] = [ai, bi] represents a connection between servers ai and bi. 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 servers.

Return all critical connections in the network.

Examples

Example 1:

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

Justification: Removing either [0, 1] or [1, 2] will split the network into separate parts, making some servers unreachable from others.

Example 2:

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

Justification: Removing [2, 3] will isolate server 3, making it unreachable from the other servers.

Example 3:

Input: n = 6, connections = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]]
Expected Output: [[1, 3]]

Justification: Removing [1, 3] will disconnect servers 3, 4, and 5 from the rest of the network.

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.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Critical Connections in a Network — problem

0. Pattern family

Family: Hard graph / bridges (Tarjan low-link)

1. Why / judgment (K3)

Critical connection = bridge: an edge whose removal increases connected components. Naïve “delete each edge and DFS” is O(E(V+E)). The standout pattern is one DFS with discovery time disc[u] and low[u]: edge u–v (v child) is a bridge iff low[v] > disc[u] (no back-edge from v’s subtree to u or above). Judgment: this is undirected bridge-finding, not directed SCC Tarjan — parent handling and back-edge to parent are the sharp edges.

2. Worked complexity / derivation (K11)

Build adj list O(V+E).
One DFS: each vertex/edge processed O(1) amortized → O(V+E) time.
Arrays disc, low: O(V) space; recursion stack O(V) worst path.
Naïve: for each edge remove+DFS connectivity → O(E·(V+E)) — reject for large E.
Example n=5, edges 5: O(V+E)=O(1) small; scales to 1e5 with O(V+E).

3. Pattern + recognition + when-NOT (K12)

Name: TARJAN BRIDGES (disc/low)

Recognition: undirected connected network; list edges whose removal disconnects; “critical connections / bridges / single points of failure on edges.”

When-NOT: Articulation points (vertices) → different low condition. Directed graphs → bridges formalize differently (need 2-edge-CC / Dominators). Weighted min-cut multi-edge → flow, not single DFS bridges.

4. Edge hand-run (K13)

n=5 edges [[0,1],[1,2],[2,3],[3,4],[2,4]]
cycle 2-3-4 → no bridge inside; 0-1 and 1-2 are bridges (leaf chain).
Output any order of [[0,1],[1,2]].
Tree edges all bridges. Single edge graph → that edge. Completely cyclic 3-cycle → [].

5. Interviewer follow-ups & drills

Q1. low[v] > disc[u] meaning?
Model answer: v’s subtree cannot reach u or ancestors without the tree edge u–v → bridge.

Q2. Why ignore parent edge as back-edge?
Model answer: Undirected: parent edge is the tree edge itself, not an alternate path.

Q3. low[v] == disc[u]?
Model answer: Back-edge from subtree to u → not a bridge (u still ties subtree).

✅ Solution Critical Connections in a Network

Problem Statement

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

Return all critical connections in the network.

Examples

Example 1:

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

Justification: Removing either [0, 1] or [1, 2] will split the network into separate parts, making some servers unreachable from others.

Example 2:

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

Justification: Removing [2, 3] will isolate server 3, making it unreachable from the other servers.

Example 3:

Input: n = 6, connections = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]]
Expected Output: [[1, 3]]

Justification: Removing [1, 3] will disconnect servers 3, 4, and 5 from the rest of the network.

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.

Solution

To solve this problem, we can use Depth First Search (DFS). The key idea is to identify bridges in the graph. A bridge is an edge that, when removed, splits the graph into disconnected parts. By using DFS, we can record the discovery and low-link values of each node. The discovery time is the time at which a node is first visited, and the low-link value is the smallest discovery time reachable from the node. If a node cannot reach an ancestor node through its descendants, then the edge leading to that descendant is a critical connection.

This approach is effective because it systematically explores all nodes and edges using DFS, ensuring that all potential critical connections are examined. The use of discovery and low-link values helps in efficiently identifying critical connections with a time complexity of , where V is the number of nodes and E is the number of edges.

Step-by-Step Algorithm

Initialize Data Structures:
- Create an adjacency list graph to represent the network of servers.
- Create arrays disc and low to store the discovery times and the lowest discovery times reachable for each node, initialized to -1.
- Initialize a list res to store the critical connections.
- Set a global time variable to track the discovery time during DFS.
Build the Graph:
- For each connection [u, v] in connections, add v to the adjacency list of u and u to the adjacency list of v.
DFS Function:
- Define a recursive DFS function that takes the current node u, its parent node parent, the disc, low, graph, and res as arguments.
- Set disc[u] and low[u] to the current time, then increment time.
- For each neighbor v of u in the graph:
  - If v is the parent of u, skip it.
  - If v has not been visited (disc[v] == -1):
    - Recursively call DFS on v with u as the parent.
    - Update low[u] to the minimum of low[u] and low[v].
    - If low[v] > disc[u], add [u, v] to res as it is a critical connection.
  - If v has already been visited and is not the parent, update low[u] to the minimum of low[u] and disc[v].
Run DFS:
- Call the DFS function starting from node 0 with -1 as the parent.
Return Result:
- Return the list res containing all the critical connections.

Algorithm Walkthrough

Let's walk through the algorithm with n = 5 and connections = [[0, 1], [1, 2], [2, 3], [3, 4], [2, 4]].

Initialize Data Structures:
- graph = [[], [], [], [], []]
- disc = [-1, -1, -1, -1, -1]
- low = [-1, -1, -1, -1, -1]
- res = []
- time = 0
Build the Graph:
- After processing connections:
  - graph = [[1], [0, 2], [1, 3, 4], [2, 4], [3, 2]]
Run DFS starting from node 0:
- DFS on node 0:
  - disc[0] = 0, low[0] = 0, time = 1
  - Visit neighbor 1.
- DFS on node 1:
  - disc[1] = 1, low[1] = 1, time = 2
  - Skip neighbor 0 (parent).
  - Visit neighbor 2.
- DFS on node 2:
  - disc[2] = 2, low[2] = 2, time = 3
  - Skip neighbor 1 (parent).
  - Visit neighbor 3.
- DFS on node 3:
  - disc[3] = 3, low[3] = 3, time = 4
  - Skip neighbor 2 (parent).
  - Visit neighbor 4.
- DFS on node 4:
  - disc[4] = 4, low[4] = 4, time = 5
  - Skip neighbor 3 (parent).
  - Visit neighbor 2.
  - Node 2 has been visited already, and it's not the parent of node 4. Update low[4] = min(low[4], disc[2]) = min(4, 2) = 2.
- Backtrack to node 3: low[3] = min(low[3], low[4]) = min(3, 2) = 2.
  - low[4] > disc[3] is not true (2 > 3 is false). So [3, 4] is not a critical connection.
- Backtrack to node 2: low[2] = min(low[2], low[3]) = min(2, 2) = 2.
  - Visit neighbor 4 again.
  - Node 4 has been visited already, and it's not the parent of node 2. Update low[2] = min(low[2], disc[4]) = min(2, 4) = 2.
  - Backtrack to node 1: low[1] = min(low[1], low[2]) = min(1, 2) = 1.
  - low[2] > disc[1] is true (2 > 1 is true). So [1, 2] is a critical connection. Add [1, 2] to res.
- Backtrack to node 0: low[0] = min(low[0], low[1]) = min(0, 1) = 0.
  - low[1] > disc[0] is true (1 > 0 is true). So [0, 1] is a critical connection. Add [0, 1] to res.
Result:
- res = [[1, 2], [0, 1]].

The final result is [[1, 2], [0, 1]], meaning removing either of these connections will split the network into separate parts.

Code

java

import java.util.*;

public class Solution {

  private int time = 0; // Time counter used in DFS

  public List<List<Integer>> criticalConnections(
    int n,
    List<List<Integer>> connections
  ) {
    // Initialize graph, discovery time and low time arrays
    List<Integer>[] graph = new ArrayList[n];
    int[] disc = new int[n],
      low = new int[n];
    Arrays.fill(disc, -1); // Mark all nodes as unvisited
    List<List<Integer>> res = new ArrayList<>();

    // Build the graph
    for (int i = 0; i < n; i++) {
      graph[i] = new ArrayList<>();
    }
    for (List<Integer> conn : connections) {
      graph[conn.get(0)].add(conn.get(1));
      graph[conn.get(1)].add(conn.get(0));
    }

    // Perform DFS from the first node
    dfs(0, -1, disc, low, graph, res);

    return res;
  }

  private void dfs(
    int u,
    int parent,
    int[] disc,
    int[] low,
    List<Integer>[] graph,
    List<List<Integer>> res
  ) {
    disc[u] = low[u] = ++time; // Initialize discovery and low times
    for (int v : graph[u]) {
      if (v == parent) continue; // Skip the parent node
      if (disc[v] == -1) {
        // If v is not visited
        dfs(v, u, disc, low, graph, res);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) {
          // Check for a critical connection
          res.add(Arrays.asList(u, v));
        }
      } else {
        low[u] = Math.min(low[u], disc[v]); // Update low time of u
      }
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    // Example 1
    int n1 = 5;
    List<List<Integer>> connections1 = Arrays.asList(
      Arrays.asList(0, 1),
      Arrays.asList(1, 2),
      Arrays.asList(2, 3),
      Arrays.asList(3, 4),
      Arrays.asList(2, 4)
    );
    System.out.println(sol.criticalConnections(n1, connections1)); // [[2, 3], [3, 4]]

    // Example 2
    int n2 = 4;
    List<List<Integer>> connections2 = Arrays.asList(
      Arrays.asList(0, 1),
      Arrays.asList(0, 2),
      Arrays.asList(1, 2),
      Arrays.asList(2, 3)
    );
    System.out.println(sol.criticalConnections(n2, connections2)); // [[2, 3]]

    // Example 3
    int n3 = 6;
    List<List<Integer>> connections3 = Arrays.asList(
      Arrays.asList(0, 1),
      Arrays.asList(1, 2),
      Arrays.asList(2, 0),
      Arrays.asList(1, 3),
      Arrays.asList(3, 4),
      Arrays.asList(4, 5),
      Arrays.asList(5, 3)
    );
    System.out.println(sol.criticalConnections(n3, connections3)); // [[1, 3]]
  }
}

Complexity Analysis

Time Complexity: The algorithm runs in time, where V is the number of vertices (servers) and E is the number of edges (connections). This is because we perform a DFS traversal of the graph, visiting each vertex and edge once.

Space Complexity: The space complexity is due to the storage required for the graph representation and the recursion stack used by the DFS algorithm.

🎯 STRICT STANDOUT — Solution Critical Connections in a Network

0. Pattern family

Family: Hard graph / Tarjan bridge DFS

1. Why / judgment (K3)

Implementation is one DFS from node 0 (problem guarantees connectivity). Set disc[u]=low[u]=timer++; for unvisited child update low[u]=min(low[u],low[v]) and emit bridge if low[v]>disc[u]; for visited non-parent, low[u]=min(low[u],disc[v]). Standout requires the parent skip and the strict > (not ≥).

2. Worked complexity / derivation (K11)

Walkthrough n=5 [[0,1],[1,2],[2,3],[3,4],[2,4]]:
DFS 0→1→2→3→4; 4 sees 2 as back → low[4]=disc[2]; 3 updates; edge 3-4 not bridge.
2-3: low[3]≤disc[2] no bridge. 1-2: low[2]>disc[1]? after cycle low[2]≤disc[2];
chain 0-1,1-2 remain bridges once low correctly set from subtree without escaping above 1.
Time: each of 5 edges examined twice undirected → O(V+E).

3. Pattern + recognition + when-NOT (K12)

Name: DISC/LOW BRIDGE TEMPLATE

Recognition: template: timer, disc/low -1, parent arg, emit when low[child]>disc[u].

When-NOT: Do not use directed SCC low-link rules unchanged. Do not BFS-layer “critical” hacks.

4. Edge hand-run (K13)

disconnected? problem says any server can reach others — one DFS enough.
Multiple edges same pair: if multiplicity ≥2, neither is bridge — simple adj may need multiedge care.
Self-loops never bridges.

5. Interviewer follow-ups & drills

Q1. ≥ vs >?
Model answer: ≥ would mark edges into articulation-style cases incorrectly as bridges.

Q2. Stack space?
Model answer: O(V) recursion; iterative stack possible if limits tight.

Q3. Output order?
Model answer: Any order; tests usually sort or compare as sets.

🧩 Pattern · Graphs

Recognize it: Nodes + edges, reachability / shortest-unweighted / cycles / components → BFS or DFS with a visited set.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Critical Connections in a Network? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Critical Connections in a Network** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Critical Connections in a Network** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Critical Connections in a Network**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Critical Connections in a Network**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Minimize Malware Spread II Rectangle Area II →