백준 11724 - 연결 요소의 개수


Tags : DFS


문제

백준 11724 - 연결 요소의 개수

image


풀이

image

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool chk[1001];
vector<int> v[1001];

void DFS(int x)
{
	chk[x] = true;

	for (int i = 0; i < (int)v[x].size(); ++i)
	{
		int next = v[x].at(i);

		if (next != 0 && !chk[next])
			DFS(next);
	}
}

int main()
{

	int ans = 0;

	int N, M = 0;
	cin >> N >> M;

	for (int i = 0; i < M; ++i)
	{
		int x, y = 0;
		cin >> x >> y;

		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int i = 1; i <= N; ++i)
	{
		if (!chk[i])
		{
			DFS(i);
			++ans;
		}
	}

	cout << ans << '\n';
}