6장 그래프 - (3) 그래프 탐색 문제 1 - 연결 요소(11724번)

1. 연결 요소(11724번)

1) 연결 요소(Connected Component) 

- 그래프가 아래 그림과 같이 연결되어 있지 않은 경우가 있을 수도 있다.

- 이렇게 나누어진 각 각의 그래프를 연결 요소라고 한다.

- 연결 요소는 해당 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.

- 또, 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

- 아래 그래프는 총 2개의 연결 요소로 이루어져 있다.

- 연결 요소를 구하는 것은 DFS나 BFS 탐색을 이용해서 구할 수 있다.

2) 정답 코드

#include <iostream>

#include <vector>

using namespace std;

vector<int> a[1001];

bool check[1001];

void dfs(int x) {

check[x] = true;

for (int i = 0; i < a[x].size(); i++) {

int y = a[x][i];

if (check[y] == false)

dfs(y);

}

}

int main(void) {

int n, m;

scanf("%d %d", &n, &m);

for (int i = 0; i < m; i++) {

int u, v;

scanf("%d %d", &u, &v);

a[u].push_back(v);

a[v].push_back(u);

}

int components = 0;

for (int i = 1; i <= n; i++) {

if (check[i] == false) {

dfs(i);

components++;

}

}

printf("%d\n", components);

return 0;

}