Isolated Network Groups
EasyGraphs
Problem
An office has n computers numbered 0 to n - 1. Each pair [a, b] in edges is a cable linking two computers; cables work both ways.
Computers that can reach each other through cables, directly or through other computers, form one network group. Return the number of network groups.
Example 1
- Input:
- n = 5, edges = [[0,1],[1,2],[3,4]]
- Output:
- 2
The groups are {0, 1, 2} and {3, 4}.
Example 2
- Input:
- n = 4, edges = []
- Output:
- 4
With no cables, every computer is a group on its own.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ edges.length ≤ 2 · 10^5
- 0 ≤ a, b < n
Hint
Show the first hint
Each group is a connected component of the graph.
Walkthrough
How to approach it
01Clarify before coding
- Are cables bidirectional? Yes.
- Does a computer with no cables count as a group? Yes, a group of one.
- Can a cable connect a computer to itself? Yes; it does not change anything.
02Brute force
Give each computer its own label and repeatedly sweep the edges, copying the smaller label across each cable until labels stop changing; count distinct labels.
Cost: Up to O(V) sweeps of O(E) each: O(V · E), far too slow for a 10^5-node chain.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.