Step to developing a usable algorithm:
Model the problem
Find a algorithm to solve it.
Fast enough? Fit in memory?
If not, figure out why?
Find a way to address the problem.
Iterate until satisfied.

Dynamic connectivity:
Given a set of N objects

Union command: connect two object.
find /connected query: is there a path connecting the two objects?

When programming, convenient to name objects 0 to N - 1.
Use integers as array index.
Suppress details not relevant to union-find.

Modeling the connections
Assume “is connected to” is an equivalence relation:
Reflexive: p is connected to p.
symmetric : if p is connected to q, then q is connected to p.
Transitive: if p is connected to q and q is connected to r, then p is connected to r.

Connected components. Maximal set of objects that are mutually connect.
{ 0 } { 1 4 5 } { 2 3 7 6 }

Implementing the operation
Find query. Check if two objects are in the same component.
Union command. Replace components containing two objects with their union.

Union-find data type(API)
Goal. Design efficient data structure for union-find.
Number of objects N can be huge.
Number of operation M can be huge.
Find queries and union command may be intermixed.

Dynamic-connectivity client
Read in number of objects from standard input.
Repeat:
Read in pair of integers from standard input
If they are not yet connected, connect the and print out pair.