연결 요소 찾기

무방향 그래프의 연결 요소란 어떤 주어진 정점에서 도달할 수 있는 정점들의 부분집합을 말합니다. 그래프가 무방향이므로, 연결 요소에 속한 모든 정점은 서로 도달할 수 있습니다.

$n$개의 정점과 $m$개의 간선을 가진 무향 그래프 $G$가 주어집니다. 이 그래프의 모든 연결 요소를 찾아야 합니다. 즉, 그래프의 정점들을 여러 그룹으로 나누되, 같은 그룹 안에서는 어떤 정점에서든 다른 모든 정점으로 갈 수 있고, 서로 다른 그룹 사이에는 경로가 존재하지 않도록 해야 합니다.

문제를 해결하기 위해 깊이 우선 탐색을 수정하여, 어떤 컴포넌트의 정점에서 시작했을 때 그 컴포넌트의 모든 정점, 즉 도달 가능한 모든 정점에 해당 컴포넌트의 지정된 번호를 표시하도록 합니다. 이를 위해 used 배열을 각 정점의 컴포넌트 번호를 저장하는 배열로 바꾸고, 처음에는 0으로 채워 둡니다:

const int maxn = 1e5;
int component[maxn]; // тут будут номера компонент

void dfs(int v, int num) {
    component[v] = num;
    for (int u : g[v])
        if (!component[u]) // если номер не присвоен, то мы там ещё не были
            dfs(u, num);
}

이제 일련의 탐색을 수행합시다. 먼저 첫 번째 정점에서 탐색을 시작하면, 이 탐색이 방문한 모든 정점이 첫 번째 연결 요소를 이룹니다. 그다음 남은 정점 중 아직 방문하지 않은 첫 번째 정점을 찾아 그 정점에서 탐색을 시작하면, 두 번째 연결 요소를 찾게 됩니다. 모든 정점이 표시될 때까지 이 과정을 반복합니다.

이는 매우 간결하게 작성할 수 있습니다:

int num = 0;
for (int v = 0; v < n; v++)
    if (!component[v])
        dfs(v, ++num);

이렇게 하면 변수 num에는 연결 요소의 개수가 저장되고, 배열 component에는 각 정점이 속한 연결 요소의 번호가 저장됩니다. 이 배열은 예를 들어 주어진 두 정점 사이에 경로가 존재하는지를 빠르게 확인하는 데 사용할 수 있습니다.

최종 시간 복잡도는 $O(n + m)$입니다. 이 알고리즘은 같은 정점에서 두 번 실행되지 않으며, 각 간선은 정확히 두 번(한쪽 끝에서 한 번, 다른 쪽 끝에서 한 번) 확인되기 때문입니다.