1. 개요

1.1. 문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

1.2. 입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

1.3. 출력

첫째 줄에 연결 요소의 개수를 출력한다.

문제 링크: 11724번: 연결 요소의 개수

2. 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <iostream>
#include <vector>

std::vector<int> g_graph[1'001] = {};
bool g_isVisited[1'001] = {};
int g_connComponentCount = 0;

void Dfs(int v)
{
    // 방문 처리
    g_isVisited[v] = true;

    // 방문한 적 없는 모든 연결 정점에 대해 Dfs
    for (const int& w : g_graph[v])
    {
        if (!g_isVisited[w])
        {
            Dfs(w);
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N = -1;
    int M = -1;
    std::cin >> N >> M;

    // 간선 입력
    for (int i = 0; i < M; ++i)
    {
        int u = -1;
        int v = -1;
        std::cin >> u >> v;

        g_graph[u].push_back(v);
        g_graph[v].push_back(u);
    }

    // 모든 정점을 순회하며 연결 요소 개수 업데이트
    for (int v = 1; v <= N; ++v)
    {
        if (g_isVisited[v])
        {
            continue;
        }

        Dfs(v);
        ++g_connComponentCount;
    }

    std::cout << g_connComponentCount;

    return 0;
}

3. 분석

그래프에서 연결 요소는 서로 도달 가능한 정점들의 부분 집합을 의미합니다. 무방향 그래프에서 연결 요소의 개수를 찾기 위해 사용한 전략은 다음과 같습니다.

  1. 모든 정점 순회를 시작합니다.
  2. 정점을 방문했는지 확인하고 방문한 적 있다면 다음 정점으로 넘어가고, 방문한 적 없다면 Dfs를 수행합니다.
  3. Dfs를 수행하여 도달 가능한 모든 정점에 대해 방문 처리 합니다. 이 과정이 하나의 연결 요소의 모든 정점을 방문하는 것이므로 Dfs가 끝나면 연결 요소 개수를 1 증가시킵니다.
  4. 모든 정점 순회가 끝났을 땐 그래프의 연결 요소 개수 세기가 끝납니다.

각 정점을 1번만 방문하고, 정점 방문 시 연결된 간선을 순회하므로 시간 복잡도는 O(V + E)가 됩니다.