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

문제출처: https://www.acmicpc.net/problem/11724

풀이

그래프를 그려서 연결 요소의 개수를 세주면 됩니다. 무방향그래프이기 때문에 u->v, v->u 길을 모두 1처리해줘야합니다.

코드

#include<iostream>
using namespace std;
int map[1001][1001];
int check[1001];
int n, m, u, v, cnt;
void dfs(int x);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i=0;i<m;i++)
	{
		cin >> u >> v;
		map[u][v] = 1;
		map[v][u] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		if(!check[i])
		{
			dfs(i);
			cnt++;
		}
	}
	cout << cnt << '\n';
}
void dfs(int x)
{
	check[x] = 1;
	for (int i = 1; i <= n; i++)
	{
		if (!check[i] && map[x][i])
			dfs(i);
	}
}

결과