문제

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

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

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)

둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

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

예제

---

풀이

https://jdselectron.tistory.com/49

DFS 또는 BFS로 그래프를 순회하고 나서 방문 처리가 되지 않은 정점이 있으면 끊어진 그래프라고 볼 수 있다. 따라서 이러한 DFS 또는 BFS가 몇번 다시 호출되는지를 카운트 하면 연결 요소의 개수를 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;

bool visited[1001]; 
vector<int> graph[1001]; 

void dfs(int x){
	visited[x] = true;
	for(int i = 0; i < graph[x].size(); i++){
		int y = graph[x][i];
		if(!visited[y]){
			dfs(y); 
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	// 모든 노드가 연결되어 있으면, cnt가 1이고 dfs는 다시 호출되지 않음. 
	// 끊어진 그래프여서 방문 처리가 되지 않은 노드가 있으면, 
	// cnt가 1보다 커지고 dfs 다시 호출됨. 
	int cnt = 0; 
	for(int i = 1; i <= n; i++){
		if(!visited[i]){ 
			cnt++;  
			dfs(i); 
		}
	}

	cout << cnt; 
	
	return 0;
}