[백준 4803] 트리

문제 링크 => https://www.acmicpc.net/problem/4803

4803번: 트리

---

트리 문제이다.

 

이 문제의 핵심은 정점 2개가 주어질 때 방향이 존재하지 않는다는 것이다. 

 

즉, a b 가 입력되면 a => b 가 될 수 있고, b => a 가 될 수 있다는 소리다.

 

따라서 이를 고려해서 코드를 작성해야 한다. (이부분을 몰라서 계속 틀렸다.)

 

임의의 정점들의 간선으로 이어진 그래프에 대해서 Cycle 이 존재하면 해당 그래프를 무시하도록 하고, 정상적인 트리인 경우 1을 카운팅하고 간선으로 이어지지 않은 하나의 정점 또한 1을 카운팅하면 된다.

 

Cycle 이 존재하는지 판단하는 여부는 Queue에 하나의 정점을 넣는것이 아니라 이전 정점과 현재 정점을 동시에 넣어서 다음 정점으로 이동할 때, 방문된 경우에는 Queue 에 현재 정점과 다음 정점을 push 하고 방문되지 않은 경우에는 항상 이전 정점과 다음 정점이 같아야 한다.

 

만약에 다른 경우에는 해당 그래프는 Cycle이 되고 모든 순회를 마친 경우 Cycle이면 0, 아니면 1을 반환하도록 한다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#define DIV 1000000007

using namespace std;

vector<int> v[501];
bool visited[501];

void init(int n) {
	for (int i = 1; i <= n; i++) {
		v[i].clear();
		visited[i] = false;
	}
}

void input(int m) {
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

int bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ -1,start });
	visited[start] = true;
	int ret = 1;
	while (!q.empty()) {
		int before = q.front().first;
		int cur = q.front().second;
		q.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i];
			if (!visited[next]) {
				q.push({ cur,next });
				visited[next] = true;
			}
			else {
				if (before != next) ret = 0;
			}
		}
	}
	return ret;
}

void solve(int cnt, int n) {
	int result = 0;
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) result += bfs(i);
	}
	if (result == 0) cout << "Case " << cnt << ": No trees." << endl;
	else if (result == 1) cout << "Case " << cnt << ": There is one tree." << endl;
	else cout << "Case " << cnt << ": A forest of " << result << " trees." << endl;
}

int main() {

	int cnt = 1, n, m;
	while (1) {
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		init(n);
		input(m);
		solve(cnt++, n);
	}

	return 0;
}