Dsa
Union Find
Warm-up
Group Students by Club Membership
You are given a list of students, where each student is represented by a unique integer ID. Additionally, you have a list of pairs, where each pair indicates that two students are in the same club. Your task is to find out how many distinct clubs are there and list the IDs of students in each club.
Input Format:
- The first line contains an integer n (1 ≤ n ≤ 1000), the total number of students.
- The second line contains an integer m (0 ≤ m ≤ 10000), the number of pairs of students belonging to the same club.
- The next m lines each contain two integers a and b (1 ≤ a, b ≤ n), indicating that student a and student b are in the same club.
Output Format:
- The first line should output the number of distinct clubs.
- The following lines should output the student IDs belonging to each club in sorted order, one club per line.
Example:
Input:
5
3
1 2
2 3
4 5
Output:
2
1 2 3
4 5
Key concepts
union_findgroupingarrays
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