C++ 백준 11724번

백준 11724번 www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

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

 

이 문제는 dfs나 bfs로 그래프를 순회하고 나서 방문되지 않은 vertex가 있으면 끊어진 그래프이다. 그래서 이 새로운 dfs(bfs)가 몇 번 다시 시작됐는지만 찾아보면 된다!!

#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() {
	int n, m;
	cin >> n >> m;
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!check[i]) {
			cnt++; // 새로운 dfs가 시작될때마다 1씩 증가
			dfs(i);
		}
	}
	cout << cnt << endl;
}