백준 4803: 트리

문제 요약

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 트리
• DFS
• 분리 집합

문제 풀이

주어진 그래프를 탐색하면서, 이미 방문한 곳을 방문했다면 사이클이 형성되므로 트리가 아니고, 계속해서 탐색된다면 트리이다.

DFS탐색으로 풀었는데, 결국 이것이 트리인지 아닌지가 중요하므로 dfs()는 bool타입을 리턴해준다. a->b로의 경로가 존재한다면 b->a로의 경로가 존재하므로, 바로 이전에 방문했던 노드를 재방문하는 경우는 없어야 한다.

풀이 코드

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

using namespace std;

multimap<int, int> mm;
bool visited[501];
int n;

bool dfs(int idx, int prev) {
	visited[idx] = true;
	auto rg = mm.equal_range(idx);
	for (auto& it = rg.first; it != rg.second; it++) {
		if (it->second == prev) continue;
		if (visited[it->second]) return false;
		if (!dfs(it->second, idx)) return false;
	}
	return true;
}

int main() {
	int n, m, in1, in2, cnt;
	for (int i = 1;; i++) {
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0) break;
		mm.clear();
		cnt = 0;
		memset(visited, 0, sizeof(visited));
		for (int j = 0; j < m; j++) {
			scanf("%d%d", &in1, &in2);
			mm.insert({ in1,in2 });
			mm.insert({ in2,in1 });
		}
		for (int j = 1; j <= n; j++) {
			if (!visited[j]) {
				if (dfs(j, 0)) cnt++;
			}
		}
		if (cnt == 0) printf("Case %d: No trees.\n", i);
		else if (cnt == 1) printf("Case %d: There is one tree.\n", i);
		else printf("Case %d: A forest of %d trees.\n", i, cnt);
	}
	return 0;
}

후일담

이 문제 정말 이해가 안되서 못풀었는데, 단순히 그냥 간선으로 연결된 그래프 안에 사이클이 존재하면 그 그래프는 트리가 아닌 것으로 체크해주면 되는 거였다.