March 24
Union Find
What union find means, when connecting and querying components quickly matters more than traversing everything each time.
What it is
Union find is a structure for maintaining groups of connected elements.
It is good at answering two questions:
- are these two items in the same group?
- how do I merge these groups now?
When to use it
It appears when connectivity changes as the process goes on:
- connecting nodes
- detecting components
- checking whether a new edge creates a cycle
Common mistake
The classic mistake is doing a full traversal every time a new connection appears.
If the problem has many unions and many connectivity checks, that scales badly.
Better question
Before using it, ask:
- does the problem talk about groups gradually merging?
- will I query connectivity many times?
- is the graph changing over time?
Share this page
Copy the link manually from the field below.