Show problems as
Classic problem #323MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Number of Connected Components in an Undirected Graph

Real-world version: Counting Separate Clusters of Workshops
Tracked in this browser only
Read Number of Connected Components in an Undirected Graph on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A campus has n workshops numbered 0 through n - 1. Each entry links[i] = [a, b] is a walkway between workshop a and workshop b that may be used in either direction.

Two workshops belong to the same cluster when some run of walkways leads from one to the other. Every workshop belongs to a cluster, even one no walkway touches.

Return how many clusters the campus has.

Examples

Example 1

Input
n = 6, links = [[0, 1], [1, 2], [4, 5]]
Output
3

Workshops 0, 1 and 2 hang together through two walkways, 4 and 5 make a pair, and 3 stands alone, which is three clusters.

Example 2

Input
n = 6, links = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
Output
1

The walkways form one long run through every workshop, so the whole campus is a single cluster.

Example 3

Input
n = 4, links = [[0, 1], [1, 2], [0, 2]]
Output
2

The third walkway joins a pair already linked through workshop 1, so it merges nothing. Workshops 0, 1 and 2 make one cluster and workshop 3 makes another.

Constraints

  • 1 <= n <= 2000
  • 1 <= links.length <= 5000
  • links[i].length == 2
  • 0 <= links[i][j] <= n - 1
  • The two ends of a walkway are different workshops.
  • No walkway is listed twice.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_components(n: int, links: list[list[int]]) -> int:
Java
public int countComponents(int n, int[][] links)

More on the same topics