Loading...
Loading...
Loading...
A hostel has n students, numbered 1 to n. The warden has a list of m friendships. Each friendship joins two students, and it works both ways.
A friend group is a set of students who are linked through a chain of friendships: friends, friends of friends, and so on. A student with no friends is a group of one.
Print the number of friend groups in the hostel.
Example 1
Input
6 3 1 2 2 3 4 5
Output
3
The groups are {1, 2, 3}, {4, 5} and {6}. Student 6 has no friends but is still a group.
Example 2
Input
4 0
Output
4
No friendships, so every student is a group of one.
Try the problem first. Open one hint at a time.
Start from any student and visit everyone you can reach through friendships. All of them form one group.
Keep a visited array. A student who is already visited belongs to a group you have counted.
Loop over every student from 1 to n. Each time you find one who is not visited, that is a new group: count it and visit the whole group.
Mark a student as visited when you add them to the queue, not when you take them out.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor