Posted on 2008-06-02 09:57
superman 閱讀(336)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1268 C++ 00:00.00 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int s, t, c = 1;
9 while(true)
10 {
11 cin >> s >> t;
12 if(s == -1 && t == -1)
13 break;
14
15 cout << "Case " << c++;
16
17 if(s == 0 && t == 0)
18 {
19 cout << " is a tree." << endl;
20 continue;
21 }
22
23 int cnt[2008] = { 0 };
24 bool x[2008] = { false };
25
26 x[s] = x[t] = true;
27 int max = 0;
28 max >?= s;
29 max >?= t;
30
31 cnt[t]++;
32 while(cin >> s >> t && s && t)
33 cnt[t]++, max >?= s, max >?= t, x[s] = x[t] = true;
34
35 //count the number of roots
36 int rootCnt = 0;
37 for(int i = 1; i <= max; i++)
38 if(x[i] && cnt[i] == 0)
39 rootCnt++;
40 if(rootCnt != 1)
41 {
42 cout << " is not a tree." << endl;
43 continue;
44 }
45
46 //check if each node has only one parent
47 int i;
48 for(i = 1; i <= max; i++)
49 if(x[i] && cnt[i] > 1)
50 break;
51 if(i <= max)
52 {
53 cout << " is not a tree." << endl;
54 continue;
55 }
56
57 cout << " is a tree." << endl;
58 }
59
60 return 0;
61 }
62