[C/C++] 백준 - 4803번 (트리)

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

4803번: 트리

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

 

그래프 문제이면서 트리 문제이고 동시에 분리 집합 문제이기도 한 짬뽕문제이다.

어느 알고리즘으로 풀던 간 이 문제를 제대로 이해만 하면 어렵지 않은 문제인데 나는 이 문제를 어렵게 풀었다.

시험기간이 끝난 후 약 2주만에 PS를 하려니 제대로 되지도 않았고, 내가 많이 사용했던 코드들도 많이 틀렸다.

역시 무엇이든 꾸준함이 답인듯.

 

어쨋든 이 문제는 그래프 속 순환구조를 따져 그래프 내의 트리 조건에 충족하는 트리의 개수를 출력하는 문제이다.

그래프의 구현은 C++의 벡터를 이용하여 어렵지 않게 구현할 수 있고, 그래프 내 트리의 존재유무는 깊이 우선 탐색을 이용하여 그래프 내 순환을 찾는 알고리즘을 사용해야한다.

 

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

int N, M, answer;
bool visited[503];
vector<int> adj[503];

bool DFS(int index, int parentIndex) {
	visited[index] = true;
	for (auto head : adj[index]) {
		if (!visited[head]) {
			if (DFS(head, index)) return true;
		}
		else if (parentIndex != head) return true;
	}
	return false;
}

int main(){
	fastio;
	int count = 0;
	while (1) {
		answer = 0;
		cin >> N >> M;
		if (N == 0 && M == 0) break;
		for (int i = 1; i <= 500; i++) adj[i].clear();
		while (M--) {
			int from, to;
			cin >> from >> to;
			adj[from].push_back(to);
			adj[to].push_back(from);
		}
		memset(visited, false, sizeof(visited));
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				if (!DFS(i, -1)) answer++;
			}
		}

		cout << "Case " << ++count;
		if (answer == 0) cout << ": No trees." << endl;
		else if (answer == 1) cout << ": There is one tree." << endl;
		else cout << ": A forest of " << answer << " trees." << endl;
	}
	return 0;
}