[백준] 알고리즘 11724번 - 연결 요소의 개수 문제

#include <bits/stdc++.h>
using namespace std;
vector<int> v[1001];
bool check[1001];
void dfs(int x) {
	check[x] = true;
	int size = v[x].size();
	for (int i = 0; i < size; i++) {
		if (check[v[x][i]] == false)
			dfs(v[x][i]);
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m,cnt=0;
	cin >> n >> m ;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (!check[i]) {
			dfs(i);
			cnt++;
		}
	}
	cout << cnt;
}

연결요소 개수의 문제는 정점과의 연결이 끊긴 그래프의 개수를 구해주면된다.

DFS, BFS를 이용해 쉽게 해결할 수 있다.

저는 DFS를 이용하여 문제를 해결하였습니다.

방문하지 않은 노드가 있을 경우 카운트를 해주면서 구해주면된다.