Pattern visualizer
Redundant Connection
A tree on n nodes has exactly n - 1 edges and no cycles, so one extra edge in the stream must be the one that closes a loop somewhere. You don't need to see the whole shape to find it: track, for every node, which connected group it belongs to (its DSU root), and merge two groups every time an edge joins them. The one edge whose two ends are ALREADY in the same group is the answer — nothing before it could have connected them any other way, so it is provably the newest cycle-closer. The badge on each node below is its current root. Animated on: 7 nodes, edges [1,2] [3,4] [1,3] [5,6] [1,5] [6,7] [4,7] in that order (an undirected tree plus one extra edge) — which edge can be removed to leave a valid tree?.
Union-Find: the edge whose endpoints already share a root
Stream of edges — one too many for a tree
7 nodes and 7 edges. A tree over 7 nodes needs exactly 6 edges, so this stream has one extra — process them left to right and the extra one reveals itself the instant its two ends already share a root.
1FUNCTION findRedundant(n, edges):2 FOR i FROM 1 TO n3 parent[i] <- i4 FOR EACH (u, v) IN edges5 ru <- FIND(parent, u)6 rv <- FIND(parent, v)7 IF ru = rv8 RETURN [u, v]9 UNION(parent, ru, rv)10 RETURN []
← / → step · space play · Home restart