Count Connected Components in Server Network

GraphUnion Find

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.

Example 1

Input

[
  "5",
  "[[0,1],[1,2],[3,4]]"
]

Output

Explanation. Servers 0, 1, and 2 form one cluster, while servers 3 and 4 form a second cluster. Total clusters = 2.

Example 2

Input

[
  "4",
  "[[0,1],[2,3]]"
]

Output

Explanation. Servers 0 and 1 are connected, and servers 2 and 3 are connected, resulting in 2 distinct clusters.

Example 3

Input

[
  "4",
  "[[0,1],[1,2],[2,3]]"
]

Output

Explanation. All 4 servers are connected into a single cluster.

Example 4

Input

[
  "3",
  "[]"
]

Output

Explanation. With no connections present, each server forms its own independent cluster.

Example 5

Input

[
  "5",
  "[[0,1],[0,1],[1,0]]"
]

Output

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?

Constraints:

1 <= n <= 1000 0 <= connections.length <= 2000 connections[i].length == 2 0 <= u, v < n Connections may include duplicate connections or self-loops.

Views: 2