Graphs
Union-find
A structure that answers are these two joined, and merges groups, both in nearly constant time.
Key idea
The question traversal answers badly
Traversal tells you the components of a graph you already have. It is a poor fit when edges arrive one at a time and you must answer connectivity questions as they do, because each new edge would mean traversing again.
Union-find handles exactly that. It maintains a partition into groups, supports merging two groups, and answers which group is this in, all in close to constant time.
Key idea
Each group is a tree with a representative
Every element points at a parent. Following parents leads to a root, and that root is the group's representative. Two elements are in the same group exactly when they have the same root.
Merging two groups is one assignment: point one root at the other. That is why it is fast.
Why it works
The return value of union is the useful part
union reporting False means the two were already connected, so the edge being added closes a cycle rather than joining anything. Reporting True means two separate groups have just become one.
Almost every question in this family is answered by watching that boolean rather than by inspecting the structure afterwards. Before reaching for anything else, ask what the sequence of Trues and Falses would tell you, because it is usually the whole answer and it costs nothing to collect.
Key idea
Path halving keeps the trees flat
The line inside find that points each node at its grandparent shortens the path a little on every lookup. Over many operations the trees stay almost flat, which is what makes the operations effectively constant time.
The full analysis gives an inverse Ackermann factor, which is below 5 for any input that fits in memory. Quote it as effectively constant and say amortized, since a single early operation can still walk a longer path.
Tip
Union by size or rank
Attaching the smaller tree under the larger keeps depth down and is the other half of the standard optimization. Without it, a chain of unions in the wrong order can build a long path before compression flattens it.
Path compression alone is enough in practice for interview inputs. Mention union by size as the companion optimization; implementing both is a few extra lines and is worth doing if the problem stresses performance.
Key idea
What makes a graph a tree
A graph on n nodes is a tree exactly when any two of these three hold: it is connected, it has no cycle, and it has n minus 1 edges. Any two of the three force the third, which is the fact worth carrying out of this section.
That is convenient here, because it means you never have to test all three. Pick the two that your structure already tells you cheaply, and say out loud why the third follows.
Cost
Cost
Each operation is effectively constant, so processing e edges over n elements is close to O(n plus e). Space is one array of size n.
Compared with rebuilding a traversal per query, which is O(n plus e) each time, the difference is the entire reason the structure exists.
Union-find drills
Build the structure, then read it twice. find returns a root, compressing as it goes. union joins two groups and reports whether they were separate. largest_group returns the size of the biggest group once every edge has been applied. edges_until_connected returns how many edges had to be processed before everything became one group, or -1 if that never happens.
Tests
print(largest_group(5, [(0, 1), (1, 2), (3, 4)]), largest_group(3, []), largest_group(0, [])) print(edges_until_connected(4, [(0, 1), (2, 3), (1, 2)]), edges_until_connected(4, [(0, 1), (2, 3)]), edges_until_connected(1, [])) parent = make(4) print(union(parent, 0, 1), union(parent, 1, 0)) print(find(parent, 0) == find(parent, 1))
Output
Run the tests when you are ready.
Number Of Connected Components In An Undirected Graph
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Graph Valid Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Redundant Connection
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.