[BOJ 11724] 연결요소의 개수 C++

난이도: Silver 2
번호: 11724
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

11724번: 연결 요소의 개수

C++

DFS

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

int N, M, cnt = 0;
bool visited[1001];
vector<int> V[1001];
queue<int> Q;

void DFS(int start)
{
    visited[start] = true;
    for (int j = 0; j < V[start].size(); j++)
        if (!visited[V[start][j]])
            DFS(V[start][j]);
}

int main(void)
{
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);

    // node, path
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }

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

    cout << cnt;
}

C++

BFS

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

int N, M, cnt = 0;
bool visited[1001];
vector<int> V[1001];
queue<int> Q;

void BFS(int start)
{
    visited[start] = true;
    Q.push(start);
    while (!Q.empty())
    {
        int cur = Q.front();
        Q.pop();
        for (int j = 0; j < V[cur].size(); j++)
            if (!visited[V[cur][j]])
            {
                visited[V[cur][j]] = true;
                Q.push(V[cur][j]);
            }
    }
}

int main(void)
{
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);

    // node, path
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }

    for (int i = 1; i <= N; i++)
        if (visited[i] == false)
        {
            BFS(i);
            cnt++;
        }

    cout << cnt;
}