백준 11724: 연결 요소의 개수

문제 요약

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS

문제 풀이

DFS혹은 BFS로 탐색하면서 연결된 요소의 개수를 파악하는 문제이다.

방문 여부를 알기 위해 bool타입의 visited[]를 만들었고, 1번부터 n번까지의 정점을 순서대로 탐색하였다.

단, 정점방문을 최초로 시작할 때에 해당 정점을 방문하지 않았다면 cnt++과 함께 탐색을 시작하고,

그렇지 않으면 탐색하지 않았다.

정점 간의 간선은 multimap을 이용하여 표현하였고, multimap의 eqaul_range()로 연결된 다른 정점들의 집합을 찾았다.

나는 DFS로 풀었지만, BFS로도 풀 수 있을거라 생각한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

bool visited[1001];
multimap<int, int> mp;
int cnt = 0;

void dfs(int v) {
	visited[v] = true;
	auto p = mp.equal_range(v);
	for (auto& it = p.first; it != p.second; it++) {
		if (!visited[it->second])
			dfs(it->second);
	}
}

int main()
{
	int n, m, in1, in2;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> in1 >> in2;
		mp.insert({ in1, in2 });
		mp.insert({ in2, in1 });
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			cnt++;
			dfs(i);
		}
	}
	cout << cnt;
	return 0;
}