[코딩테스트] [BOJ11724] 연결 요소의 개수

문제

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

---

풀이

1. 간선 정보 포함한 무방향 그래프를 이중벡터로 만들어준다

2. 노드 방문 여부 확인용 벡터를 만들어준다

3. 순차적으로 노드를 방문하며 인접한 노드에 대해 bfs를 수행하고, 방문 체크를 해준다
   3-1. 해당 노드를 방문하지 않았다면, 새로운 시작점으로 간주하고 count를 증가시킨다

---

코드

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

int main()
{
	int nodeCount = 0, edgeCount = 0;
	cin >> nodeCount >> edgeCount;

	vector<vector<int>> adj(nodeCount);
	for (int i = 0; i < edgeCount; i++)
	{
		int left = 0, right = 0;
		cin >> left >> right;

		adj[left - 1].push_back(right - 1);
		adj[right - 1].push_back(left - 1);
	}

	int count = 0;
	vector<bool> visited(nodeCount, false);
	for (int i = 0; i < nodeCount; i++)
	{
		if (visited[i])
		{
			continue;
		}

		count++;

		queue<int> bfs;
		bfs.push(i);
		visited[i] = true;

		while (!bfs.empty())
		{
			int current = bfs.front();
			bfs.pop();

			for (int next : adj[current])
			{
				if (!visited[next])
				{
					visited[next] = true;
					bfs.push(next);
				}
			}
		}
	}

	cout << count;

	return 0;
}