Dsa
Union Find
Hard
Community Connection
In a city, there are multiple communities and roads connecting them. You have been given a list of connections, and your task is to determine how many distinct communities exist after all the connections are processed. The communities might change over time as new roads are added.
Input Format:
- The first line contains an integer n: the number of total communities (1 ≤ n ≤ 2000).
- The second line contains an integer m: the number of connections (1 ≤ m ≤ 5000).
- The next m lines contain pairs of integers (a, b) indicating a road connecting community a and community b.
Output Format:
- Print the number of distinct communities after processing all connections.
Example:
Input:
5
4
1 2
2 3
4 5
1 4
Output:
2
Key concepts
union_findpath_compression
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now