[210603][백준/BOJ] 11724번 연결 요소의 개수

문제

입출력

풀이

방문하지 않은 노드에 대해 DFS를 돌리면서 DFS를 돌린만큼 cnt++를 하면 연결 요소의 개수를 구할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
#define SIZE 1002

int board[SIZE][SIZE];
bool vis[SIZE];
int n, m, x, y, cnt = 0;

void DFS(int V)
{
	vis[V] = 1;
	for (int i = 1; i <= n; ++i)
	{
		if (!vis[i] && board[V][i])
			DFS(i);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		cin >> x >> y;
		board[x][y] = 1;
		board[y][x] = 1;
	}
	
	for (int i = 1; i <= n; ++i)
	{
		if (!vis[i])
		{
			DFS(i);
			cnt++;
		}
	}
	cout << cnt;
}