[C++] 백준 11724번 연결 요소의 개수 (Silver 2)

풀이

Stack으로 구현한 DFS로 문제를 해결했다.

for loop 시작에서 i번째 노드 방문 체크를 통해 연결요소의 개수를 카운트했다. 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    ///freopen("11724.txt", "r", stdin);

    int N, M, u, v;
    cin >> N >> M;
    vector<vector<int>> graph(N+1);
    for (int i = 0; i < M; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> visited(N+1, 0);
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (visited[i]) continue;
        stack<int> stk;
        stk.push(i);

        while (!stk.empty()) {
            int v = stk.top();
            stk.pop();

            if (visited[v]) continue;

            visited[v] = 1;
            for (int i = 0; i < graph[v].size(); i++) {
                if (visited[graph[v][i]] == 0)
                    stk.push(graph[v][i]);
            }
        }
        ans++;
    }
    cout << ans << endl;
    return 0;
}