[BOJ/백준] 11724번. 연결 요소의 개수 - C++[cpp]

문제

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

 

 

 

무방향 그래프에서 연결 요소를 찾는 문제

틀렸던 부분

N개의 노드가 있고, 1개의 간선이 있다고 하자. 그러면 연결 요소는 1개가 아니라 N-2개여야 한다. 즉, 연결되어있지 않은 노드들을 고려하지 않아서 2트한 문제이다.

 

코드

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

bool vis[1002];
unordered_set<int> sub;
vector<int> adj[1002];

void DFS(int start) {
    vis[start] = 1;
    sub.erase(start);
    for (int i = 0; i < adj[start].size(); i++) {
        int next = adj[start][i];
        if (!vis[next]) {
            DFS(next);
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, count;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int s, e;
        cin >> s >> e;
        adj[s].push_back(e);
        adj[e].push_back(s);
        sub.insert(s);
        sub.insert(e);
    }

    // 정점이 연결되어 있지 않는 부분도 고려해야 한다
    count = n - sub.size();

    while (!sub.empty()) {
        DFS(*sub.begin());
        count++;
    }
    cout << count;
}

 

방문했던 곳인지를 O(1)에 확인하기 위해서 Hash Set(unordered_set)을 사용해봤는데, 과연 이게 실행시간에 도움이 되는지는 잘 모르겠다 ㅎㅎ. 재귀가 아닌 Stack을 이용하여 문제를 풀면 아마 시간을 조금 더 단축할 수 있을 듯