백준 - 11724. 연결 요소의 개수

문제

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

입력

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

 

출력

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

 

풀이법

다음 입력 예제를 보고 먼저 손으로 그려봅시다.  

6	5
1	2
2	5
5	1
3	4
4	6

정점의 개수 N = 6, 간선의 개수 M = 5이기 때문에 첫 번째 입력을 받고 5번을 더 입력 받아야 하는군요.

두 번째 입력부터 무방향 그래프의 정점을 그려보면 다음과 같습니다. 

각 그래프를 인접리스트에 담아 순회하면서 시작점부터 연결된 정점을 방문하고, 더 이상 방문할 정점이 없으면 다음 그래프로 넘어가 연결된 정점을 방문하면 되겠습니다. 각 그래프에서 시작할 때 횟수를 카운트하면 연결된 요소의 개수를 확인할 수 있겠군요. 그러면 코드로 구현해 보겠습니다.

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

const int max_n = 1001;
vector<int> adj[max_n];
int visited[max_b];
int vertex, edge, u, v, cnt = 0;

void dfs(int current) { // (1)
	visited[current] = 1; 
	for(int there : adj[current]) {
		if(visited[there] == 0) dfs(there);	
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> vertex >> edge;
	for(int i = 0 ; i < edge ; i++) {
		cin >> u >> v; 
		adj[u].push_back(v); // (2)
		adj[v].push_back(u);
	}
	
	for(int i = 1 ; i <= vertex ; i++) {
		if(visited[i] == 0) { // (3)
			dfs(i);
			cnt++;
		}
	}
	cout << cnt << "\n";
	return 0;
}

(1) dfs() 함수는 현재 시작점에서 연결되어 있는 정점을 모두 탐색합니다. 방문배열에 없는 정점일 때 재귀호출을 합니다.

(2) 문제에서 무방향 그래프라고 명시했기 때문에 양방향으로 인접리스트에 담습니다.

(3) 정점의 개수만큼 순회하면서 방문한 적이 없는 정점을 방문합니다. 연결된 정점은 재귀호출을 하면서 방문을 할테니 이 조건에서의 횟수를 카운트하면 연결된 요소의 개수가 됩니다.