Log inSign up
hardLeetCodeNot Started

Critical Connections in a Network

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network 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 each other. Return all critical connections in the network in any order.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

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 each other (i.e. a bridge in an undirected graph).

Return *all critical connections in the network in any order*.

---

### Examples

Example 1: ``text Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted. Removing [1, 3] disconnects server 3 from the rest of the network (0, 1, 2). Removing any edge in the cycle [0, 1, 2] does not disconnect the graph.

Example 2: ``text Input: n = 2, connections = [[0,1]] Output: [[0,1]] Explanation: Removing [0, 1] disconnects server 0 and server 1.

---

### Constraints - 2 <= n <= 10^5 - n - 1 <= connections.length <= 10^5 - 0 <= a_i, b_i <= n - 1 - a_i != b_i - There are no repeated connections. - The network is connected.

Constraints:

  • 2 <= n <= 105
  • n - 1 <= connections.length <= 105
  • 0 <= a_i, b_i <= n - 1
  • a_i != b_i
  • There are no repeated connections
  • The network is connected

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand graph bridges and critical network connection concepts.
  • Master Tarjan's tin and low array mechanics for bridge detection.
  • Differentiate tree-edges from back-edges in undirected DFS trees.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find edges whose deletion disconnects the graph
  • Network vulnerability analysis, critical links or single points of failure
  • Bridges in an undirected graph

Algorithmic Decision Tree:

  • 1. Maintain tin (entry time) and low (lowest reachable time) arrays, both initialized to -1.
  • 2. Start DFS from node 0 with parent = -1 and global timer = 0.
  • 3. For each neighbor v of u:
  • - If v == parent, skip.
  • - If v is visited, update low[u] = min(low[u], tin[v]) (back-edge).
  • - If v is unvisited, recurse dfs(v, u), update low[u] = min(low[u], low[v]). If low[v] > tin[u], record [u, v] as a bridge.
  • 4. Return recorded bridges.

Connected Patterns:

Articulation Points in GraphTarjan's Strongly Connected ComponentsBiconnected Components

1. Edge Removal Connectivity Check

Intuition

Simulate removing each connection one-by-one. Run BFS/DFS to check if all n vertices remain reachable.

Algorithm

  1. Initialize critical = [].
  2. For each edge connections[i] = [u, v]:
  3. Construct graph excluding connections[i].
  4. Run BFS from node 0.
  5. Count visited vertices.
  6. If visited count < n, append [u, v] to critical.
  7. Return critical.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 std::vector<std::vector<int>> criticalConnections(int n, std::vector<std::vector<int>>& connections) {
8 std::vector<std::vector<int>> bridges;
9
10 for (size_t skip = 0; skip < connections.size(); ++skip) {
11 std::vector<std::vector<int>> adj(n);
12 for (size_t i = 0; i < connections.size(); ++i) {
13 if (i == skip) continue;
14 adj[connections[i][0]].push_back(connections[i][1]);
15 adj[connections[i][1]].push_back(connections[i][0]);
16 }
17
18 std::vector<bool> visited(n, false);
19 std::queue<int> q;
20 q.push(0);
21 visited[0] = true;
22 int count = 0;
23
24 while (!q.empty()) {
25 int u = q.front();
26 q.pop();
27 count++;
28 for (int v : adj[u]) {
29 if (!visited[v]) {
30 visited[v] = true;
31 q.push(v);
32 }
33 }
34 }
35
36 if (count < n) {
37 bridges.push_back(connections[skip]);
38 }
39 }
40 return bridges;
41 }
42};
43
44int main() {
45 Solution sol;
46 std::vector<std::vector<int>> conn = {{0,1},{1,2},{2,0},{1,3}};
47 auto res = sol.criticalConnections(4, conn);
48 std::cout << "Critical connections count: " << res.size() << " (Expected: 1)\n";
49 if (!res.empty()) std::cout << "Bridge: [" << res[0][0] << ", " << res[0][1] << "]\n";
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(E * (V + E))
  • Space complexity: O(V + E)

2. Cycle Ranking DFS (Tree Level & Back-Edge Mark)

Intuition

Assign DFS tree depths to vertices. When a back-edge connects to an ancestor, mark the entire cycle as non-critical.

Algorithm

  1. Build adjacency list for the undirected graph.
  2. Assign ranks (depths) starting at 0 for root.
  3. Define dfs(u, depth):
  4. Set rank[u] = depth.
  5. Maintain minRank = depth.
  6. For each neighbor v in adj[u]:
  7. If v == parent, skip.
  8. If rank[v] != -1, minRank = min(minRank, rank[v]) (back-edge).
  9. Else: recurse recRank = dfs(v, depth + 1).
  10. If recRank <= depth, edge (u, v) is part of a cycle.
  11. Else: edge (u, v) is a bridge! Add to answer.
  12. minRank = min(minRank, recRank).
  13. Return minRank.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6 int dfs(int u, int p, int depth, const std::vector<std::vector<int>>& adj,
7 std::vector<int>& rank, std::vector<std::vector<int>>& bridges) {
8 rank[u] = depth;
9 int minRank = depth;
10
11 for (int v : adj[u]) {
12 if (v == p) continue;
13 if (rank[v] != -1) {
14 minRank = std::min(minRank, rank[v]);
15 } else {
16 int recRank = dfs(v, u, depth + 1, adj, rank, bridges);
17 if (recRank > depth) {
18 bridges.push_back({u, v});
19 }
20 minRank = std::min(minRank, recRank);
21 }
22 }
23 return minRank;
24 }
25public:
26 std::vector<std::vector<int>> criticalConnections(int n, std::vector<std::vector<int>>& connections) {
27 std::vector<std::vector<int>> adj(n);
28 for (const auto& c : connections) {
29 adj[c[0]].push_back(c[1]);
30 adj[c[1]].push_back(c[0]);
31 }
32
33 std::vector<int> rank(n, -1);
34 std::vector<std::vector<int>> bridges;
35 dfs(0, -1, 0, adj, rank, bridges);
36 return bridges;
37 }
38};
39
40int main() {
41 Solution sol;
42 std::vector<std::vector<int>> conn = {{0,1},{1,2},{2,0},{1,3}};
43 auto res = sol.criticalConnections(4, conn);
44 std::cout << "Bridges: [" << res[0][0] << ", " << res[0][1] << "] (Expected: [1, 3])\n";
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

3. Tarjan's Bridge-Finding Algorithm (Gold Standard)

Intuition

Single-pass DFS tracking entry time tin[u] and lowest reachable ancestor time low[u]. An edge (u, v) is a bridge if low[v] > tin[u].

Algorithm

  1. Initialize tin and low arrays of size n with -1.
  2. Set timer = 0.
  3. Define dfs(u, parent):
  4. tin[u] = low[u] = ++timer.
  5. For each neighbor v in adj[u]:
  6. If v == parent, continue.
  7. If tin[v] != -1 (already visited):
  8. low[u] = min(low[u], tin[v]) (back-edge update).
  9. Else (tree edge):
  10. dfs(v, u).
  11. low[u] = min(low[u], low[v]).
  12. If low[v] > tin[u]:
  13. Record [u, v] as a critical connection.
  14. Call dfs(0, -1).
  15. Return recorded critical connections.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6 int timer = 0;
7
8 void dfs(int u, int parent, const std::vector<std::vector<int>>& adj,
9 std::vector<int>& tin, std::vector<int>& low,
10 std::vector<std::vector<int>>& bridges) {
11 tin[u] = low[u] = ++timer;
12
13 for (int v : adj[u]) {
14 if (v == parent) continue;
15
16 if (tin[v] != -1) {
17 // Back-edge to an ancestor
18 low[u] = std::min(low[u], tin[v]);
19 } else {
20 // Forward tree-edge
21 dfs(v, u, adj, tin, low, bridges);
22 low[u] = std::min(low[u], low[v]);
23
24 // Bridge condition
25 if (low[v] > tin[u]) {
26 bridges.push_back({u, v});
27 }
28 }
29 }
30 }
31public:
32 std::vector<std::vector<int>> criticalConnections(int n, std::vector<std::vector<int>>& connections) {
33 std::vector<std::vector<int>> adj(n);
34 for (const auto& c : connections) {
35 adj[c[0]].push_back(c[1]);
36 adj[c[1]].push_back(c[0]);
37 }
38
39 std::vector<int> tin(n, -1);
40 std::vector<int> low(n, -1);
41 std::vector<std::vector<int>> bridges;
42 timer = 0;
43
44 dfs(0, -1, adj, tin, low, bridges);
45 return bridges;
46 }
47};
48
49int main() {
50 Solution sol;
51 std::vector<std::vector<int>> conn = {{0,1},{1,2},{2,0},{1,3}};
52 auto res = sol.criticalConnections(4, conn);
53 std::cout << "Tarjan Bridges Count: " << res.size() << " (Expected: 1)\n";
54 if (!res.empty()) {
55 std::cout << "Bridge: [" << res[0][0] << ", " << res[0][1] << "] (Expected: [1, 3])\n";
56 }
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Edge Removal Connectivity CheckO(E * (V + E))O(V + E)Simulates removing each edge and runs BFS/DFS to test connected component count.Repeated full graph traversals
2.Cycle Ranking DFSO(V + E)O(V + E)Tracks recursion depths and marks cycle back-edges as non-critical.Recursion depth
3.Tarjan's Bridge-Finding AlgorithmOptimalO(V + E)O(V + E)Calculates discovery time (tin) and lowest reachable time (low). Bridge iff low[v] > tin[u].Single DFS traversal

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not skipping the parent vertex, falsely treating the undirected edge back to parent as a back-edge.

Pitfall 2:

Updating low[u] = min(low[u], low[v]) on a back-edge instead of using tin[v].

Pitfall 3:

Using low[v] >= tin[u] instead of strictly greater (>): >= is the condition for Articulation Points, NOT bridges!

Crucial Edge Cases to Validate:

  • Tree structure (n vertices, n - 1 edges) — Every single edge is a bridge; all n - 1 edges are returned.
  • Complete cycle (e.g. 0-1-2-0) — low values equal tin[root] for all nodes; returns an empty array [].
  • Two cycles joined by a single edge (dumbbell graph) — The connector edge between the two cycles has low[v] > tin[u] and is identified as the only bridge.
  • Minimal graph n = 2 with one edge — The single edge is returned as a bridge.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify bridge vs articulation point: 'A bridge is an edge whose removal disconnects the graph, while an articulation point is a vertex whose removal disconnects it.'
  2. State the bridge condition cleanly: 'Edge (u, v) is a bridge if and only if low[v] > tin[u] (strictly greater, not greater than or equal).'
  3. Emphasize complexity: Tarjans algorithm achieves optimal O(V + E) time in a single pass, which easily handles 105 servers.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In Tarjan's bridge-finding algorithm, what does the condition low[v] > tin[u] signify?

2.Why do we skip the immediate parent edge (v == parent) during the DFS traversal of neighbor edges?

3.When encountering a back-edge to a previously visited vertex v, why do we update low[u] using tin[v] instead of low[v]?

Back to DSA Sheet