Approach Summary
Union-Find or DFS on adjacency matrix. Count the number of distinct roots (connected components) after processing all edges.
How to Recognize This Pattern
- "How many groups of directly/indirectly connected cities"
- Same as number of connected components
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(n)
Tags
DFS BFS Union-Find Graph