Loading...
Loading...
Loading...
A college computer lab has n computers, numbered 1 to n. A cable joins two computers in both directions. Two computers are in the same network if you can go from one to the other along cables, maybe through other computers.
The lab in-charge wants to know how many separate networks there are. A computer with no cables is a network on its own. Print the number of networks.
Example 1
Input
5 3 1 2 2 3 4 5
Output
2
Computers 1, 2 and 3 form one network, and 4 and 5 form another.
Example 2
Input
4 0
Output
4
No cables, so every computer is its own network.
Try the problem first. Open one hint at a time.
Start with every computer in its own group, so there are n groups.
Each cable either joins two different groups into one, or connects two computers already in the same group.
Keep a parent array where each group has one leader. A find method follows parents up to the leader.
For each cable, find both leaders. If they differ, point one leader at the other and lower the group count by 1.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor