Graphs & Networks
Union Find
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
connected?groupsmerge accountsnumber of provincesredundant connectiondynamic connectivity
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Dynamically merging groups and asking “same set?”
- Count components as edges arrive?
- Find with path compression, union by rank.
Classic problem
Number of Provinces (LeetCode 547) — isConnected[i][j] === 1 means cities i and
j are directly linked. Count the connected groups. Start with n groups and merge.
Input: isConnected = [[1,1,0,0,0,0], [1,1,0,1,0,0], [0,0,1,1,0,0], [0,1,1,1,0,0], [0,0,0,0,1,1], [0,0,0,0,1,1]]
Output: 2 — cities {0,1,2,3} merge into one province and {4,5} form the other.
Common pitfalls
No path compression → near-O(n) finds.
Counting components wrong after unions.