[C/C++] 백준 11724번 - 연결 요소의 개수

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int N, M, u, v, ans;
bool visit[1001];
vector<int> graph[1001];
queue<int> q;

void BFS(int x)
{
	q.push(x);
	visit[x] = true;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int next : graph[now])
		{
			if (!visit[next])
			{
				visit[next] = true;
				q.push(next);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

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

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

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

 

 

 

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수