11724 연결 요소의 개수(BFS)

로그인

해결 방법:

• 방향 없는 그래프를 인접 리스트로 표현합니다.
• 그래프의 모든 정점에 대해 BFS 탐색을 수행합니다.
• BFS 탐색을 수행하면서 방문한 정점들을 모두 체크합니다. 이 과정에서 연결된 모든 정점들은 같은 연결 요소에 속하므로, 탐색이 끝나면 연결 요소의 개수를 증가시킵니다.
• 탐색이 끝난 후, 연결 요소의 개수를 출력합니다.

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

vector<vector<int>> vec;
vector<bool> isvisit;

int result = 0;

void bfs(int n);

// 11724
int main()
{
	
	int V, E;
	cin >> V >> E;
	vec.resize(V + 1);
	isvisit.resize(V + 1);

	for (int i = 1; i <= E; i++)
	{
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}

	for (int i = 1; i <= V; i++)
	{
		if (isvisit[i] == false)
		{
			bfs(i);
			result++;
		}
	}

	cout << result;
	return 0;
}

void bfs(int n)
{
	isvisit[n] = true;

	queue<int> q;
	q.push(n);

	while (!q.empty())
	{
		int k = q.front();
		q.pop();

		for (int i = 0; i < vec[k].size(); i++)
		{
			int node = vec[k][i];
			if (isvisit[node]) continue;
			
			isvisit[node] = true;
			q.push(node);
		}
	}

}