[백준] 11724번 연결 요소의 개수

문제

https://www.acmicpc.net/problem/11724

풀이과정

먼저 문제를 풀기 전에 연결요소에 대한 개념을 찾아봤다. 연결 요소란 1~N까지 정점으로 이루어져있는 그래프가 나누어 존재할 경우 각각의 그래프를 연결 요소라고 한다. 연결 요소에 속한 모든 정점은 연결하는 경로가 있어야 하며, 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

아래 그림을 참고하면 쉽게 이해할 수 있다.

이러한 연결 요소의 개수를 세는 방법은 DFS를 이용하여 구현했다. DFS를 이용해 1부터 탐색을 시작하며 DFS(1) 이후에 check[i]가 false로 나오면 연결요소가 하나 더 있다는 뜻으로 해석했다.

소스코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> a[1001];
bool check[1001];

int N, M, ans;

void DFS(int node)
{
    check[node] = true;

    for (int i = 0; i < a[node].size(); i++)
    {
        int next = a[node][i];
        if (check[next] == false)
        {
            DFS(next);
        }
    }
}
int main()
{
    cin.sync_with_stdio(false);

    cin >> N >> M;

    while (M--)
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v); a[v].push_back(u);
    }

    for (int i = 1; i <= N; i++)
    {
        if (check[i] == false)
        {
            DFS(i);
            ans += 1;
        }
    }

    cout << ans << "\n";

    return 0;
}