Algorithm - Component Chaining

Here is the algorithm:

$1.$ Run Union-Find to identify components

$2.$ Find one representative per component

$3.$ Output $k-1$ where $k$ is the number of components

$4.$ Output edges connecting representatives in a chain The tricky part is extracting representatives from Union-Find. Loop through all nodes and collect unique component IDs. Then pick one node per ID and chain them together. Simple once you see it.