Critical Connections in a Network

Critical Connections in a Network

What is this problem about?

The Critical Connections in a Network interview question asks you to find all "bridges" in an undirected graph. A bridge is an edge that, if removed, would increase the number of connected components in the graph. In networking terms, these are the single points of failure where a single cable cut would disconnect parts of the network.

Why is this asked in interviews?

Microsoft and Amazon frequently ask this Hard graph coding problem to test a candidate's knowledge of advanced graph algorithms, specifically Tarjan’s Algorithm or Fleury’s Algorithm concepts. It evaluates your ability to use DFS to find cycles and identify edges that are not part of any cycle. It’s a classic test of technical depth in graph theory.

Algorithmic pattern used

The problem is solved using a DFS-based Bridge Finding Algorithm (Tarjan's/Rank-based).

1. Maintain an array discoveryTime to store when each node was first visited.
2. Maintain an array lowLink to store the lowest discoveryTime reachable from the node (excluding its parent edge).
3. During DFS, if a child node $v$ has lowLink[v] > discoveryTime[u], then the edge $(u, v)$ is a critical connection (bridge).
4. This works because a lowLink value less than or equal to the parent's discoveryTime indicates a back-edge exists, meaning there is a cycle and the edge is not a bridge.

Example explanation

Nodes: 0-1, 1-2, 2-0, 1-3.

1. DFS starts at 0. disc[0]=0.
2. Moves to 1. disc[1]=1.
3. Moves to 2. disc[2]=2.
4. From 2, finds 0. Cycle! low[2] becomes 0.
5. Backtrack to 1. low[1] becomes 0.
6. From 1, moves to 3. disc[3]=3.
7. 3 has no other edges. low[3] stays 3.
8. low[3] (3) > disc[1] (1). Edge (1, 3) is a critical connection.

Common mistakes candidates make

• O(E * (V+E)) Complexity: Trying to remove each edge one by one and checking connectivity with BFS/DFS. This is too slow for large graphs.
• Parent Handling: Forgetting to ignore the edge back to the immediate parent during the lowLink update, which would incorrectly make every edge look like part of a cycle.
• Directed Graph Logic: Applying directed graph cycle detection to an undirected graph problem.

Interview preparation tip

Bridges and Articulation Points are common "Hard" graph topics. Memorizing the relationship between discovery times and low-link values is the key to solving almost all of them in linear time.