Editorial for Connected Components

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Build an adjacency list for the undirected graph.

Scan vertices from $1$ ~1~ to $n$ ~n~. If the current vertex has not been labelled yet, it starts a new component. Run BFS from that vertex and assign the same component number to every reachable vertex. Because BFS visits exactly the vertices connected to the start vertex, each connected component gets one label. Scanning vertices in increasing order gives the required component numbering.

Each vertex is enqueued at most once and each undirected edge is inspected twice, so the time complexity is $O(n + m)$ ~O(n + m)~. The memory complexity is $O(n + m)$ ~O(n + m)~.

Solution (Python)

import sys
from collections import deque


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m = data[0], data[1]
    graph = [[] for _ in range(n)]
    pos = 2
    for _ in range(m):
        a = data[pos] - 1
        b = data[pos + 1] - 1
        pos += 2
        graph[a].append(b)
        graph[b].append(a)

    labels = [0] * n
    component = 0
    queue: deque[int] = deque()

    for start in range(n):
        if labels[start] != 0:
            continue

        component += 1
        labels[start] = component
        queue.append(start)

        while queue:
            v = queue.popleft()
            for to in graph[v]:
                if labels[to] == 0:
                    labels[to] = component
                    queue.append(to)

    sys.stdout.write(str(component) + "\n")
    sys.stdout.write(" ".join(map(str, labels)) + "\n")


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.