[백준 C++] 11724 : 연결 요소의 개수

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

BFS, DFS 전부 다 상관없지만, 필자는 BFS를 사용하였다.

연결 요소는 간단하게 말해서 그래프의 개수이다.

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

int bfs(int start)
{
	if (visited[start])
		return 0;

	queue<int> que;
	que.push(start);
	visited[start] = true;

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

		for (int i = 0; i < graph[current].size(); i++)
		{
			int next = graph[current].at(i);
			
			if (!visited[next])
			{
				que.push(next);
				visited[next] = true;
			}
		}
	}

	return 1;
}

int main()
{
	int N, M, ans = 0;
	cin >> N >> M;

	graph = vector<vector<int>>(N + 1);
	visited = vector<bool>(N + 1, false);

	for (int i = 0; i < M; i++)
	{
		int u, v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= N; i++)
		ans += bfs(i);

	cout << ans << endl;

	return 0;
}

for문으로 각 정점마다 BFS를 돌려고 시도할 때, 이미 방문한 정점이면 return 0를 하고 방문하지 않았으면 이어져있는 모든 정점들을 방문하게 하였다.

이외의 것들은 기존 BFS랑 똑같다.