11724번: 연결 요소의 개수

https://www.acmicpc.net/problem/11724

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> VecGraph[1001];
int N{}, M{}, ConnectedComponent{};
int Check[1001];

void BFS(int Vertex)
{
	queue<int> Q;
	Q.push(Vertex);
	Check[Vertex] = 1;

	while (!Q.empty())
	{
		int CurrentVertex = Q.front();
		Q.pop();

		for (int i = 0; i < VecGraph[CurrentVertex].size(); ++i)
		{
			int ConnectedVertex = VecGraph[CurrentVertex][i];
			if (Check[ConnectedVertex] == 1)
			{
				continue;
			}
			Q.push(ConnectedVertex);
			Check[ConnectedVertex] = 1;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	//freopen("input.txt", "rt", stdin);

	cin >> N >> M;

	int u{}, v{};
	for (int i = 0; i < M; ++i)
	{
		cin >> u >> v;
		VecGraph[u].push_back(v);
		VecGraph[v].push_back(u);
	}

	for (int i = 1; i <= N; ++i)
	{
		if (Check[i] == 0)
		{
			BFS(i);
			++ConnectedComponent;
		}
	}

	cout << ConnectedComponent;

	return 0;
}