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

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

 

문제 분석

간단한 DFS활용 문제이다. 

 

입력을 받아 그래프를 만들고, 그래프를 이루고 있는 덩어리가 몇개인지 세는 형태의 문제이다. 

 

DFS를 이해했다면 무리 없이 풀 수 있는 문제라고 생각한다. 

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

static vector<vector<int>> A;
static vector<bool> visited;
void DFS(int v);

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

    int N, M;
    cin >> N >> M;
    A.resize(N+1);
    visited = vector<bool>(N+1, false);

    for (int i = 0; i < M; ++i)
    {
        int s, e;
        cin >> s >> e;
        A[s].push_back(e);
        A[e].push_back(s);
    }

    int count = 0;

    for (int i = 1; i < N + 1; ++i)
    {
        if (!visited[i])
        {
            count++;
            DFS(i);
        }
    }

    cout << count;
}

void DFS(int v)
{
    if (visited[v])
        return;

    visited[v] = true;

    for (int i : A[v])
    {
        if (visited[i] == false)
            DFS(i);
    }
}