673. Component Count
A telecom company has n relay towers numbered 0 to n-1 and a list of cables edges, where edges[i] = [a, b] joins towers a and b and carries traffic in both directions. Towers that can reach each other through any chain of cables belong to the same network.
Return the number of separate networks. A tower with no cable counts as a network of its own. The list may contain the same cable several times and cables whose two ends are the same tower; both are harmless and must not change the answer. The order of the cables does not matter. Aim for near-linear time, O((n + m) * alpha(n)), and O(n) extra space.
Example 1
- Input:
- n = 6, edges = [[0,2],[2,4],[1,5]]
- Output:
- 3
- Explanation:
Towers 0, 2 and 4 form one network, towers 1 and 5 form another, and tower 3 has no cable, so there are 3 networks.
Example 2
- Input:
- n = 4, edges = []
- Output:
- 4
- Explanation:
With no cables every tower is its own network, giving 4.
Example 3
- Input:
- n = 5, edges = [[0,1],[1,2],[2,0],[3,3]]
- Output:
- 3
- Explanation:
Towers 0, 1, 2 are linked (the cycle adds nothing new), tower 3 only has a cable to itself, and tower 4 is alone: 3 networks.
Constraints
1 ≤ n ≤ 200000
0 ≤ edges.length ≤ 200000
0 ≤ a, b < n; repeated cables and self-loops are allowed
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O((n + m) * alpha(n))
- Space
- O(n)