11724 - 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

 

0. 연결 요소란 무엇인가?

 

그래프에서 연결요소란 위의 사진과 같은 것입니다.

영어로는 Connected Component로 표현합니다.

위와 같은 형태를 글로 표현하잠면 아래와 같습니다.

 

1. 연결 요소의 노드의 쌍은 경로로 서로 연결 되어 있다. (노드 A에서 노드 B로 가는 길이 존재한다.)

2. 각각의 연결요소에서 다른 연결 요소로 가는 경로는 없다.(노란색 집합에서 녹색 집합으로 연결된 경로가 없다.)

 

구하는 방법은 의외로 간단한데, DFS나 BFS를 진행하며 더이상 탐색을 할 수 없을 경우 하나의 연결 요소를 찾게 됩니다.

모든 정점에 대해서 DFS 혹은 BFS를 진행하게 된다면 모든 연결요소를 찾을 수 있게 됩니다.

 

1. 소스코드

#include<iostream>

using namespace std;

int matrix[1001][1001] = { 0, };
int visit[1001] = { 0, };
int n, m;
int cnt = 0;
int dfs(int cur) {
	if (visit[cur] == 1) return 0;
	else visit[cur] = 1;
	for (int i = 1; i <= n; i++) {
		//연결되었다면
		if (matrix[cur][i] == 1 && visit[i] != 1) {
			dfs(i);
		}
	}
	return 1;
}

int main(void) {
	cin >> n >> m;

	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		matrix[a][b] = 1;
		matrix[b][a] = 1;
	}

	for (int i = 1; i <= n; i++) {
		if(dfs(i)) cnt++;
	}
	cout << cnt << "\n";
	return 0;
}

 

2. 마무리

다양한 용어들이 많은 이론인 만큼 개념을 확실히 정립해야 하겠습니다.