Graph Theory37 sections · 1633 units
Open in Course

Critical Connections - Edge Cases

(Single edge and cycles)

1.1. Single edge: n=2n=2, connections [[0,1]][[0,1]].

The edge is a bridge. Output: [[0,1]][[0,1]].

2.2. Complete cycle: n=3n=3, connections [[0,1],[1,2],[2,0]][[0,1],[1,2],[2,0]].

No bridges. Output: [][].

3.3. Star graph: n=4n=4, connections [[0,1],[0,2],[0,3]][[0,1],[0,2],[0,3]].

All edges are bridges because each leaf has only one connection. Output: all edges.

4.4. Disconnected graph: problem guarantees connected, but if not, run DFS from each component.