Question bank › Union Find
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
Part of InterviewLab's verified interview question bank. We show the prompt and concepts to practise with — never a copy-paste solution.