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

문제

[C++] 백준 11724: 연결 요소의 개수 SILVER 2
https://www.acmicpc.net/problem/11724

 

---

 

접근 방법

이 문제는 정점과 간선이 주어졌을 때, 그래프의 연결 요소(Connected Component) 개수를 구하는 문제이다.
그래프는 무방향 그래프이므로 간선 (u, v)가 주어지면 u ↔ v 양방향으로 연결한다.

인접 리스트(vect)로 그래프를 구성하고, visited 배열로 방문 여부를 관리한다.
아직 방문하지 않은 정점을 하나 선택해 DFS를 수행하면, 해당 DFS가 끝날 때까지 방문한 정점들은 모두 같은 연결 요소에 속한다.
따라서 DFS를 한 번 시작할 때마다 연결 요소의 개수를 1 증가시키면 된다.

 

구현 시 주의할 점

• 정점 번호가 1부터 n까지이므로, 인접 리스트와 방문 배열은 n+1 크기로 생성한다.
• 그래프의 개수는 최악의 경우 N개가 될 수 있으므로, 바깥 반복문은 N번까지 탐색하도록 구성한다.

 

---

 

코드

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

vector<vector<int>> vect;
vector<bool> visited;

void dfs(int node)
{
	visited[node] = true;
	for (int i = 0; i < vect[node].size(); i++)
	{
		int next = vect[node][i];
		if (visited[next] == false)
			dfs(next);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0, m = 0;
	cin >> n >> m;

	int u = 0, v = 0;
	vect.resize(n + 1);
	visited.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v;

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

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		bool flag = false;
		for (int j = 1; j <= n; j++)
		{
			if (visited[j] == false)  // 방문 하지 않은 그래프가 있다면
			{
				flag = true;
				dfs(j);
				cnt++;
				break;
			}
		}
		if (flag == false)
			break;
	}
	cout << cnt;

	return 0;
}