Posted on 2008-04-22 22:40
superman 阅读(337)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1141 C++ 00:03.20 5904K */
2 #include <iostream>
3
4 using namespace std;
5 const int maxn = 800;
6
7 struct { int cnt, son[maxn]; } Tree[maxn + 1];
8 struct { int cnt, x[maxn]; } Query[maxn + 1];
9
10 class DisjointSet
11 {
12 private:
13 int p[maxn + 1], rank[maxn + 1];
14 public:
15 void reset()
16 {
17 memset(p, 0, sizeof(p));
18 memset(rank, 0, sizeof(rank));
19 }
20 void make(const int x)
21 {
22 p[x] = x;
23 rank[x] = 0;
24 }
25 void link(const int x, const int y)
26 {
27 if(rank[x] > rank[y])
28 p[y] = x;
29 else
30 {
31 p[x] = y;
32 if(rank[x] == rank[y])
33 rank[y]++;
34 }
35 }
36 int find(const int x)
37 {
38 if(x != p[x])
39 p[x] = find(p[x]);
40 return p[x];
41 }
42 }set;
43
44 int ancestor[maxn + 1], cnt[maxn + 1];
45 bool black[maxn + 1];
46
47 void LCA(int u)
48 {
49 set.make(u);
50 ancestor[set.find(u)] = u;
51 for(int i = 0; i < Tree[u].cnt; i++)
52 {
53 LCA(Tree[u].son[i]);
54 set.link(u, Tree[u].son[i]);
55 ancestor[set.find(u)] = u;
56 }
57 black[u] = true;
58 for(int i = 0; i < Query[u].cnt; i++)
59 if(black[Query[u].x[i]])
60 cnt[ancestor[set.find(Query[u].x[i])]]++;
61 }
62
63 int main()
64 {
65 int n;
66 while(cin >> n)
67 {
68 memset(cnt, 0, sizeof(cnt));
69 memset(Tree, 0, sizeof(Tree));
70 memset(Query, 0, sizeof(Query));
71 memset(black, false, sizeof(black));
72
73 int s, t, m;
74 bool x[maxn] = {false};
75 for(int i = 0; i < n; i++)
76 {
77 scanf("%d:(%d)", &s, &m);
78 for(int k = 0; k < m; k++)
79 {
80 cin >> t;
81 x[t] = true;
82 Tree[s].son[k] = t;
83 }
84 Tree[s].cnt = m;
85 }
86
87 int root;
88 for(int i = 1; i <= n; i++)
89 if(x[i] == false)
90 {
91 root = i;
92 break;
93 }
94
95 cin >> m;
96 char c1, c2, c3;
97 for(int i = 0; i < m; i++)
98 {
99 cin >> c1 >> s >> c2 >> t >> c3;
100 Query[s].x[Query[s].cnt++] = t;
101 Query[t].x[Query[t].cnt++] = s;
102 }
103
104 set.reset();
105 LCA(root);
106
107 for(int i = 1; i <= n; i++)
108 if(cnt[i])
109 cout << i << ':' << cnt[i] << endl;
110 }
111
112 return 0;
113 }
114