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

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

풀이

그래프에서 연결된 덩어리들의 개수를 구하는 문제이다.
N개의 노드를 순회하면서, 한 노드에서 시작하여 DFS 탐색을 진행하고, 탐색 한 번이 끝날 때마다 연결 요소의 개수 cnt를 증가시켰다.

코드

#include <bits/stdc++.h>
using namespace std;

void dfs(int cur, vector<vector<int>>& graph, vector<bool>& visited) {
    if(visited[cur]) return;

    visited[cur] = true;
    for(int next : graph[cur]) dfs(next, graph, visited);
}

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

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N+1);

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

    int cnt = 0;
    vector<bool> visited(N+1, false);
    for(int i=1; i<=N; i++) {
        if(visited[i]) continue;

        dfs(i, graph, visited);
        cnt++;
    }
    
    cout << cnt;
    return 0;
}

시간복잡도

DFS의 시간복잡도는 O(V+E) (V는 노드, E는 간선) 인데,
이 풀이에서의 V는 N, E는 M이므로
시간복잡도는 O(N+M)이다.

개선점

BFS가 queue를 이용하는 것처럼, DFS는 stack을 이용해서 코드를 작성할 수 있다.