[ boj : 6416 ] 트리인가?

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

6416번: 트리인가?

문제 : 트리인지 아닌지 구분해서 답을 출력해라

해설 : 트리의 조건이 나와있습니다. 이에 해당하는지를 알아야 하는데 문제가 있습니다. 바로 정수의 값이 들어온다고 했는데 몇개나 들어올지 모른다는 거죠. 

이럴땐 배열을 쓰는게 아니라 map을 통해서 해결하면 됩니다.

문제에서 노드가 하나도 존재하지 않은 경우도 트리라고 했으니 이를 조심하고, 또한 루트노드는 1개만 존재하고 루트노드가 아닌 노드들은 반드시 들어오는 간선이 존재한다고 하였으니 포레스트의 개수가 2개 이상인 경우는 트리가 아닌걸로 판단합니다.

#include<bits/stdc++.h>

using namespace std;


bool solve(int t);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int u, v;
	int t = 1;
	while (true) 
		if (!solve(t++))break;	
	return 0;
}
bool solve(int t)
{
	bool ans = true;
	int u, v,root=-1;
	set<int> s;
	map<int, int> m;
	while (true) {
		cin >> u >> v;
		if (u == 0 && v == 0)break;
		else if (u < 0 && v < 0)return false;
		m[v]++;
		s.insert(u);
		s.insert(v);
	}
	for (auto u : s) {		
		if (m.find(u) == m.end()) {
			if (root == -1)
				root = u;
			else
				ans = false;
		}
		else if (m[u] > 1)
			ans = false;
	}
	if (!s.empty() && root == -1)ans = false;
	if (ans)cout << "Case " << t << " is a tree.\n";
	else cout << "Case " << t << " is not a tree.\n";
	return true;
}