hdu 1811 Rank of Tetris（拓扑排序+并查集）

不熟悉的点：
1.并查集的按秩压缩
2.vector建图
3.bfs拓扑排序
 1 #include "cstdio"
 2 #include "iostream"
 3 #include "cstring"
 4 #include "vector"
 5 #include "queue"
 6 using namespace std;
 7 const int N = 10005;
 8 int n, m, t;
 9 int fa[N];
10 int X[2 * N], Y[2 * N];
11 int son[N];
12 char O[2 * N];
13 vector<int>G[N];
14 
15 void init(int n)
16 {
17     for (int i = 0; i <= n; ++i)
18         fa[i] = -1;
19     for (int i = 0; i <= n; ++i)
20         G[i].clear();
21     memset(son, 0, sizeof(son));
22 }
23 int find(int x)
24 {
25     if (fa[x] < 0) return x;
26     return fa[x] = find(fa[x]);
27 }
28 
29 bool merg(int a, int b)
30 {
31     int x = find(a);
32     int y = find(b);
33     if (x == y) return false;
34     else if (x < y){
35         fa[x] += fa[y];
36         fa[y] = x;
37     }
38     else {
39         fa[y] += fa[x];
40         fa[x] = y;
41     }
42     return true;
43 }
44 
45 int main()
46 {
47     while (cin >> n >> m) {
48         init(n);
49         int num = n;
50         for (int i = 0; i < m; ++i) {
51             cin >> X[i] >> O[i] >> Y[i];
52             if (O[i] == '=') {
53                 if (merg(X[i], Y[i]))
54                     num--;
55             }
56         }
57         for (int i = 0; i < m; ++i) if (O[i] != '=') {
58             int x = find(X[i]);
59             int y = find(Y[i]);
60             if (O[i] == '>') {
61                 G[x].push_back(y);
62                 son[y]++;
63             }
64             else {
65                 G[y].push_back(x);
66                 son[x]++;
67             }
68         }
69         queue<int> q;
70         for (int i = 0; i < n; ++i)
71             if (son[i] == 0 && i == find(i))
72                 q.push(i);
73         int sin = 0;
74         while (!q.empty()) {
75             if (q.size() > 1) sin = 1;
76             int t = q.front();
77             q.pop();
78             --num;
79             for (int v = 0; v < G[t].size(); ++v) {
80                 if (--son[G[t][v]] == 0)
81                     q.push(G[t][v]);
82             }
83         }
84         if (num > 0) cout << "CONFLICT" << endl;
85         else if (sin) cout << "UNCERTAIN" << endl;
86         else cout << "OK" << endl;
87     }
88     return 0;
89 }