#11724 연결 요소의 개수 (C++)

링크 : www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

그림판으로 후딱 그렸다.

글만 봐서는 무슨 문제인지 감이 안잡히는데, 해당 예제 입력1을 따라 그림을 그려보면 위의 그림이 나온다.

보시다시피 결과적으로 나누어지는 연결 요소는 크게 2개로 나누어진다. 

이처럼 각 선을 연결해봤을때 최종적으로 나누어지는 연결요소의 개수를 출력하는 것이 문제의 핵심이다.

 

문제 풀이는 다음과 같았다.

 

(1) 모든 노드를 순회한다. 

(2) 이때 접근한 적이 없었던 노드(bool문이 false로 표시됨)을 발견하면, 해당 노드를 DFS한다.

(3) 해당 노드와 연결된 다른 노드 중, 접근한 적이 없었던 노드 (마찬가지로 bool문이 false로 표시됨)을 발견하면, 

또 다시 해당 노드를 DFS한다. 

 

이렇게 진행하다보면 같이 엮인 노드들은 서로 True로 이어지게 되어, 단 1개의 연결고리로 결론을 짓는다.

그리고 연결고리 1개로 종결된 True로 묶인 노드들은 재방문을 하지 않고,

접근한 적이 없는 노드(bool문이 false로 표시됨)를 향해 또 다시 DFS를 진행한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[1001];
bool check[1001] = { false, };
int n = 0, m = 0, ans = 0, temp = 0;

void dfs(int i) {
    check[i] = true;
    for (int j = 0; j < v[i].size(); j++) {
        temp = v[i][j];
        if (check[temp] == false) dfs(temp);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    int a = 0, b = 0;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (check[i] == false) {
            dfs(i);
            ans++;
        }
    }
    cout << ans << "\n";

    return 0;
}