[백준 11724] 연결 요소의 개수

문제 링크 : https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

연결요소란 말 그대로 서로 연결되어 있는 요소의 개수이다.

 

이 그래프 같은 경우 한개의 그래프가 두개의 연결요소로 분리되어 있는 것이다

만약 두 연결요소를 간선을 통해 이었을 경우에는 그래프안의 연결요소가 하나로 통합된다

---

구현방법은 dfs를 기반으로 한다

 

1번부터 n번 노드까지 순회하며

 

탐색되지 않은 노드에서부터 dfs를 시작한다

---

1번째 노드는 무조건 탐색되지 않았으므로 dfs를 시작한다

 

1번노드에서 시작한 dfs가 끝나면 1번과 연결되어 있는 모든 노드들은 탐색되게 된다

 

이런식으로 연결요소를 하나씩 제거해 나간다면

 

1부터 n번 노드까지 순회하면서 호출된 dfs의 횟수가

 

연결요소의 개수가 된다.

---

#include <iostream>
#include <algorithm>
#include <vector>
#define n_ 1005
using namespace std;

vector<int> gph[n_];
int n, m;
bool chk[n_];

void dfs(int now){
	chk[now] = true;

	for (int nxt : gph[now]){
		if (!chk[nxt]){
			dfs(nxt);
		}
	}
}

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

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

	int res = 0;
	for (int i = 1; i <= n; i++){
		if (!chk[i]){
			res++;
			dfs(i);
		}
	}
	cout << res << endl;
}