[C++][백준 11724] 연결 요소의 개수 (DFS, BFS)

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

제출 코드(DFS)

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

vector<int> vec[1001]; // 연결된 정점들을 vector에 저장
bool visit[1001]; // 방문 여부 체크용

void dfs(int node)
{
    visit[node] = true; 
    // 연결된 노드들을 체크
    for (int i = 0; i < vec[node].size(); i++)
    	// 연결된 노드 중 방문하지 않은 노드들을 dfs로 탐색
        if (!visit[vec[node][i]]) dfs(vec[node][i]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    while(m--)
    {
        int u, v;
        cin >> u >> v;
        // 방향 없는 그래프이기 때문에 u와 v 양쪽에 push
        vec[u].push_back(v);
        vec[v].push_back(u);
    }

    int cnt = 0;
    // 1부터 n번까지의 정점을 탐색
    for (int i = 1; i <= n; i++)
    {
    	// 방문하지 않은 정점이 있다면 카운트를 세고, dfs로 탐색한다
        if (!visit[i])
        {
            cnt++;
            dfs(i);
        }
    }

    cout << cnt;
}

 

제출 코드(BFS)

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

vector<int> vec[1001]; // 연결된 정점들을 vector에 저장
bool visit[1001]; // 방문 여부 체크용

void bfs(int node)
{
    queue<int> q;
    visit[node] = true;
    q.push(node);

    while (!q.empty())
    {
        int current = q.front(); // 큐의 맨 앞에서부터 bfs로 탐색
        q.pop();
        // 연결된 정점들을 체크
        for (int i = 0; i < vec[current].size(); i++)
        {
            // 연결된 정점에 방문하지 않았다면 큐에 push
            if (!visit[vec[current][i]])
            {
                q.push(vec[current][i]);
                visit[vec[current][i]] = true;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    while(m--)
    {
        int u, v;
        cin >> u >> v;
        // 방향 없는 그래프이기 때문에 u, v 양쪽에 모두 push
        vec[u].push_back(v);
        vec[v].push_back(u);
    }

    int cnt = 0;
    // 1번부터 n번 정점까지 돌아가며 체크
    for (int i = 1; i <= n; i++)
    {
    	// 아직 방문되지 않은 정점이 존재한다면 카운트를 세고, bfs로 탐색
        if (!visit[i])
        {
            cnt++;
            bfs(i);
        }
    }

    cout << cnt;
}