Module 8 · Graphs and Trees · Union Find and MST

Redundant connection

A tree plus one extra edge. Add the edges one by one: the edge whose two ends already have the same root is the one that closes the cycle.

In the forest an arrow goes from each node to its parent; rank counts the nodes in each root's tree.