0989MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Counting Separate Clusters of Workshops

Tracked in this browser only

Trains the technique from

LeetCode 323Number of Connected Components in an Undirected Graph

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_components(n: int, links: list[list[int]]) -> int:

Java

public int countComponents(int n, int[][] links)

The intended approach

Time O(n + m) near enough, for n workshops and m walkways, with the almost constant cost of the lookups.Space O(n) for the parents and cluster sizes.

Start with every workshop in a cluster of its own, so the count begins at `n`. Keep for each workshop a parent, and reach a cluster's representative by following parents up until one points at itself. Take the walkways one at a time and look up the representatives of both ends. When they already match, the walkway joins a pair that was linked already and the count is untouched. When they differ, hang the smaller cluster's representative under the larger one's and drop the count by one, since two clusters just became one. Flattening the parent chain while walking it, and always hanging the smaller side under the larger, keeps every lookup near constant. What the count reads at the end is the answer, because each walkway either merged two clusters exactly once or added nothing.

Pythonentry point: count_components

def count_components(n, links):
    parent = list(range(n))
    size = [1] * n
    def top(x):
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != root:
            parent[x], x = root, parent[x]
        return root
    clusters = n
    for pair in links:
        a = top(pair[0])
        b = top(pair[1])
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        clusters -= 1
    return clusters

The obvious version

Build the list of neighbours for every workshop, then sweep the workshops in order. Whenever one has not been reached yet, count a fresh cluster and walk outwards from it with a queue, marking every workshop the walkways lead to. Costs building the neighbour lists and one visit per workshop and walkway, and keeps no cluster bookkeeping at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_components(n, links):
    from collections import deque
    near = [[] for _ in range(n)]
    for pair in links:
        near[pair[0]].append(pair[1])
        near[pair[1]].append(pair[0])
    seen = [False] * n
    clusters = 0
    for start in range(n):
        if seen[start]:
            continue
        clusters += 1
        seen[start] = True
        queue = deque([start])
        while queue:
            here = queue.popleft()
            for there in near[here]:
                if not seen[there]:
                    seen[there] = True
                    queue.append(there)
    return clusters

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in