Count Connected Components in Server Network
Given an integer n representing servers labeled from 0 to n - 1, and a list of bidirectional connections connections where each connection is represented as a pair [u, v], compute the total number of connected server clusters.
Two servers belong to the same cluster if there is a path of network connections between them. A single isolated server with no connections forms its own cluster.
Use a Disjoint Set Union (Union-Find) data structure to keep track of cluster merges as connections are processed.
[ "5", "[[0,1],[1,2],[3,4]]" ]
Explanation. Servers 0, 1, and 2 form one cluster, while servers 3 and 4 form a second cluster. Total clusters = 2.
[ "4", "[[0,1],[2,3]]" ]
Explanation. Servers 0 and 1 are connected, and servers 2 and 3 are connected, resulting in 2 distinct clusters.
[ "4", "[[0,1],[1,2],[2,3]]" ]
Explanation. All 4 servers are connected into a single cluster.
[ "3", "[]" ]
Explanation. With no connections present, each server forms its own independent cluster.
[ "5", "[[0,1],[0,1],[1,0]]" ]
Explanation. Duplicate edges between 0 and 1 merge them into 1 cluster, while servers 2, 3, and 4 remain isolated, totaling 4 components.
Follow-up: How would you update your Union-Find implementation to also track and return the size of the largest cluster in O(1) time after all edges are processed?
1 <= n <= 1000 0 <= connections.length <= 2000 connections[i].length == 2 0 <= u, v < n Connections may include duplicate connections or self-loops.
- Views
- 12