Graph Theory37 sections · 1633 units
Open in Course

Critical Connections - Input Example

(Visualizing the network)

Input: n=4n = 4, connections = [[0,1],[1,2],[2,0],[1,3]][[0,1],[1,2],[2,0],[1,3]]. This represents graph: 010-1, 121-2, 202-0, 131-3. The first three edges form a cycle 01200-1-2-0. No edges in this cycle are critical because you can reach any vertex through alternate paths.

Edge 131-3 connects to a leaf vertex 33 with no alternate path. It is the only critical connection. If you remove 131-3, vertex 33 becomes isolated from the rest of the network.