1192. Critical Connections in a Network

At a Glance

Topic: advanced-graphs
Pattern: Tarjan bridge finding (DFS lowlink)
Difficulty: Hard
Companies: Google, Amazon, Microsoft, ByteDance, Roblox
Frequency: High
LeetCode: 1192

Problem (one-liner)

Given an undirected connected graph on n servers 0..n-1 and connections (unique undirected edges), return all bridges—edges whose removal increases the number of connected components.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Cut edge / bridge in undirected graph
Articulation / bridge = Tarjan low vs disc
low[vertex] = min discovery time reachable from subtree using at most one back edge

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute — remove each edge, BFS count components — O(E * (V+E)) — too slow.
Tarjan single DFS — O(V+E) time, O(V) space — optimal.

Optimal Solution

Go

func criticalConnections(n int, connections [][]int) [][]int {
	graph := make([][]int, n)
	for _, connection := range connections {
		from := connection[0]
		to := connection[1]
		graph[from] = append(graph[from], to)
		graph[to] = append(graph[to], from)
	}
	disc := make([]int, n)
	low := make([]int, n)
	for index := range disc {
		disc[index] = -1
	}
	bridges := [][]int{}
	clock := 0
	var dfs func(node int, parent int)
	dfs = func(node int, parent int) {
		clock++
		disc[node] = clock
		low[node] = clock
		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}
			if disc[neighbor] == -1 {
				dfs(neighbor, node)
				if low[neighbor] > disc[node] {
					bridges = append(bridges, []int{node, neighbor})
				}
				if low[neighbor] < low[node] {
					low[node] = low[neighbor]
				}
			} else {
				if disc[neighbor] < low[node] {
					// Tarjan: back edge to ancestor tightens lowlink
					low[node] = disc[neighbor]
				}
			}
		}
	}
	for start := 0; start < n; start++ {
		if disc[start] == -1 {
			dfs(start, -1)
		}
	}
	return bridges
}

JavaScript

function criticalConnections(n, connections) {
  const graph = Array.from({ length: n }, () => []);
  for (const [from, to] of connections) {
    graph[from].push(to);
    graph[to].push(from);
  }
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(0);
  const bridges = [];
  let clock = 0;
  function depthFirstSearch(node, parent) {
    clock += 1;
    disc[node] = clock;
    low[node] = clock;
    for (const neighbor of graph[node]) {
      if (neighbor === parent) {
        continue;
      }
      if (disc[neighbor] === -1) {
        depthFirstSearch(neighbor, node);
        if (low[neighbor] > disc[node]) {
          bridges.push([node, neighbor]);
        }
        low[node] = Math.min(low[node], low[neighbor]);
      } else {
        low[node] = Math.min(low[node], disc[neighbor]);
      }
    }
  }
  for (let start = 0; start < n; start += 1) {
    if (disc[start] === -1) {
      depthFirstSearch(start, -1);
    }
  }
  return bridges;
}

Walkthrough

Edge is bridge iff child low[child] > disc[parent] — no back edge from child’s subtree to parent or above. Tree edge (0,1): if 1’s subtree cannot reach ancestors of 0, edge is critical.

Invariant: After DFS returns from child, low[child] is finalized; compare to disc[parent] for bridge test.

Edge Cases

Graph not connected in problem variant — run DFS from every unvisited start (this solution covers)
Single edge n=2 — that edge is the only bridge
Multiple parallel edges (not in this problem) — need multigraph treatment

Pitfalls

Confusing tree edge with back edge — only tree edges can be bridges
Forgetting to update low when seeing visited neighbor (back/cross to ancestor)

Variants

Biconnected components — compress bridge-less blocks.
Count bridges only — same DFS, increment counter.
Dynamic bridge queries — advanced (link-cut); rarely full for interviews.

Mind-Map Tags

#tarjan #bridge #lowlink #dfs #undirected-graph #cut-edge