Dsa
Union Find
Medium
Disjoint Course Registration
In a college, there are multiple courses and students can enroll in those courses. However, some courses are incompatible (i.e., if a student is enrolled in one, they cannot enroll in another). Given a list of incompatible course pairs, your task is to find the maximum number of compatible courses that can be taken by a single student.
Input format:
- The first line contains an integer n (1 ≤ n ≤ 1000), the number of courses.
- The second line contains an integer m (0 ≤ m ≤ 10000), the number of incompatible pairs.
- The following m lines each contain two integers a and b (1 ≤ a, b ≤ n) indicating that course a and course b are incompatible.
Output format:
- Print a single integer that represents the maximum number of compatible courses.
Example:
Input:
5
4
1 2
2 3
1 3
4 5
Output:
2
Key concepts
union_findregistrationdisjoint_sets
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