[Link] https://www.acmicpc.net/problem/6416
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define endl "\n"
typedef long long ll;
const int INF = 987654321;
const int MAX = 123456;
const int log = 17;
int n;
map<int, int> deg;
map<int, vector<int>> edges;
set<int> v;
bool bfs(int root) {
queue<int> q;
q.push(root);
set<int> visit_set;
bool is_tree = true;
int v_cnt = 0;
while(!q.empty()) {
int cur = q.front(); q.pop();
if(visit_set.count(cur)) {
is_tree = false;
break;
}
visit_set.insert(cur);
v_cnt++;
for(int child: edges[cur]) q.push(child);
}
return is_tree ? v_cnt == v.size() : false;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
bool end = false;
int case_idx = 1;
while(true) {
deg.clear();
edges.clear();
v.clear();
while(true) {
int a, b; cin >> a >> b;
if(!a && !b) break;
if(a == -1 && b == -1) { end = true; break; }
v.insert(a); v.insert(b);
edges[a].push_back(b);
deg[b]++;
}
if(end) break;
if(!v.size()) {
cout << "Case " << case_idx++ << " is a tree." << endl;
continue;
}
int zero_deg_cnt = 0, root = 0;
for(int vertex: v) if(deg[vertex] == 0) { zero_deg_cnt++; root = vertex; }
if(zero_deg_cnt != 1) cout << "Case " << case_idx++ << " is not a tree." << endl;
else {
if(bfs(root)) cout << "Case " << case_idx++ << " is a tree." << endl;
else cout << "Case " << case_idx++ << " is not a tree." << endl;
}
}
return 0;
}