[백준 C++] 11724 연결 요소의 개수 - 깊이우선탐색

11724번: 연결 요소의 개수

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

vector<list<int>> Neighbors;
vector<bool> Visited;

void DFS(int Node)
{
	Visited[Node] = true;

	for (const int& Neighbor : Neighbors[Node])
	{
		if (Visited[Neighbor])
		{
			continue;
		}

		DFS(Neighbor);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	Neighbors.reserve(N);
	Visited.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Neighbors.emplace_back(list<int>());
		Visited.emplace_back(false);
	}

	for (int i = 0; i < M; ++i)
	{
		int Src, Dst;
		cin >> Src >> Dst;

		Neighbors[Src - 1].emplace_back(Dst - 1);
		Neighbors[Dst - 1].emplace_back(Src - 1);
	}

	int Count = 0;
	for (int i = 0; i < N; ++i)
	{
		if (Visited[i])
		{
			continue;
		}

		DFS(i);
		++Count;
	}
	cout << Count;
}

---

 

전체 노드를 탐색하면서 미방문 노드일 때 DFS 함수를 호출하고 카운트 +1 해주는 방식으로 풀었습니다.

DFS 함수에서는 해당 노드와 연결된 모든 노드의 방문 현황을 체크하도록 구현했습니다.