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

연결 요소의 개수

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5

1 2

2 5

5 1

3 4

4 6

예제 출력 1

2

예제 입력 2

6 8

1 2

2 5

5 1

3 4

4 6

5 4

2 4

2 3

예제 출력 2

1

 

풀이 과정

연결 요소는 간단 하게 설명하자면 예제 1번의 입력대로 그래프를 만들면 밑의 그림처럼 된다.

1, 2, 5가 한 파티션이고 3, 4, 6이 한 파티션이다.

이 파티션의 개수가 연결 요소의 개수이다.

따라서 이 그래프의 연결 요소는 2개이다. 

 

자세한 설명은 ratsgo님 블로그에 connect component를 찾아보면 된다.

https://ratsgo.github.io/data%20structure&algorithm/2017/11/24/CC/

연결요소 · ratsgo's blog

 

설명은 코드에 주석으로 달아놓았다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int n, m, from, to, cnt;
vector<int> a[1005];
bool check[500005];
 
void dfs(int n) {
    check[n] = true;
    for (int j = 0; j < a[n].size(); j++) {
        int x = a[n][j];
        if (check[x] == false) dfs(x);
    }
}
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &from, &to);
        a[from].push_back(to);
        a[to].push_back(from);
    }
 
    //dfs로 첫번째 정점부터 dfs를 시작한다.
    //dfs가 한번 끝나면 한 파티션 안의 정점의 check[i]는 true가 된다.
    //그래서 차례대로 check[i]의 false 유무를 확인하여
    //false인 i를 다시 dfs를 통해 그 파티션 안의 정점을 확인해준다.
    //그래서 dfs가 실행될 때마다 파티션이 하나씩 늘어나므로 cnt를 하나씩 늘려준다음 출력한다.
    for (int i = 1; i <= n; i++) {
        if (check[i] == false) {
            dfs(i);
            cnt++;
        }
    }
 
    printf("%d", cnt);
}