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
74
75
76
77
78
79
80
81
82
83
84
| #include <iostream>
#include <memory.h>
#include <queue>
#include <list>
using namespace std;
int u, v, tc, root;
list<int> out[1000];
bool isVisited[1000];
bool isRoot[1000];
bool isActive[1000];
bool flag;
queue<int> q;
void init() {
for(int i = 0; i < 1000; ++i)
out[i].clear();
memset(isRoot, true, sizeof(isRoot));
memset(isVisited, false, sizeof(isRoot));
memset(isActive, false, sizeof(isActive));
flag = true;
while(!q.empty()) q.pop();
}
int getRoot() {
int ret = -1;
for(int i = 0; i < 1000; ++i) {
if(!isActive[i]) continue;
if(isRoot[i] && ret == -1) {
ret = i;
}
else if(isRoot[i] && ret != -1) {
flag = false;
return -1;
}
}
if(ret == -1) flag = false;
return ret;
}
int main(void) {
while(true) {
scanf("%d %d", &u, &v);
if(u == -1) break;
init();
if(u != 0) {
while (u) {
out[u].push_back(v);
isRoot[v] = false;
isActive[v] = isActive[u] = true;
scanf("%d %d", &u, &v);
}
root = getRoot();
if (flag) {
q.push(root);
isVisited[root] = true;
while (!q.empty() && flag) {
int n = q.front();
q.pop();
for (int val : out[n]) {
if (isVisited[val]) {
flag = false;
break;
}
isVisited[val] = true;
q.push(val);
}
}
}
for (int i = 0; i < 1000 && flag; ++i) {
if (isActive[i] && !isVisited[i]) flag = flag;
}
}
if(flag) {
cout<<"Case "<<++tc<<" is a tree.\n";
} else {
cout<<"Case "<<++tc<<" is not a tree.\n";
}
}
}
|
