Algorithms / Union Find Connectivity
Least You Need to Know: Union-Find for Connectivity and Cycles
Union-find, also called **disjoint set union (DSU)**, tracks which items currently belong to the same connected component. It is especially useful when edges are added over time and you need fast connectivity or redundant-edge reasoning.
جو کم از کم جاننا ضروری ہے
- Each set has a representative root, and `find(x)` returns the representative of x's current component.
- Two nodes are connected exactly when their representatives are the same.
- When an undirected edge connects two vertices already in the same component, that edge creates a cycle.
- Path compression and union by rank or size make repeated operations very fast in practice.
- Union-find is best for dynamic connectivity under edge additions, not for general shortest-path questions.
اہم علامتیں
find(x)
representative of the set containing x
union(x, y)
merge the sets containing x and y
component
a maximal connected piece under the processed edges
مختصر حل شدہ مثال
- Start with every vertex in its own set.
- When an edge `(u,v)` arrives, compare `find(u)` and `find(v)`.
- If the representatives differ, union the two sets.
- If the representatives are already equal, the new undirected edge closes a cycle inside an existing component.
عام غلطیاں
- Students often use union-find for shortest paths even though it only answers connectivity-style questions.
- Students often forget that cycle detection with union-find is most natural for undirected graphs with added edges.
- Students often describe path compression as changing the connected components when it only speeds up future finds.
اس قسم کے سوال کو کیسے پہچانیں
- Edges are added one by one and the prompt asks whether two nodes are connected yet.
- The question asks for the first redundant edge in an undirected graph.
- You only need connectivity or component membership, not a full traversal order.
Next recommended lesson
Continue through this topic with Least You Need to Know: Z-Function, Prefix Matches, and Pattern Search by Concatenation.
Least You Need to Know: Z-Function, Prefix Matches, and Pattern Search by ConcatenationRelated lessons
Keep going with nearby lessons in the same topic.