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

 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 rank[N];
11 int X[2*N],Y[2*N];
12 int son[N];
13 char O[2*N];
14 vector<int>G[N];
15 
16 void init(int n)
17 {
18     for(int i = 0; i <= n; ++ i)
19         fa[i]=i, rank[i]=0;
20     for(int i = 0; i <= n; ++ i)
21         G[i].clear();
22     memset(son, 0,sizeof(son));
23 }
24 int find(int x)
25 {
26     return fa[x] = fa[x] == x? x :find(fa[x]);
27 }
28 
29 bool merg(int x,int y)
30 {
31     int fx = find(x);
32     int fy = find(y);
33     if (fx == fy) return false;
34     if (rank[fx] > rank[fy])
35         fa[fy] = fx;
36     else {
37         if (rank[fx] == rank[fy])
38             ++ rank[fy];
39         fa[fx] = fy;
40     }
41     return true;
42 }
43 
44 int main()
45 {
46     int u, v;
47     char ch;
48     while (cin >> n >> m) {
49         init(n);
50         int num = n;
51         for (int i = 0;i < m; ++ i) {
52             cin >> X[i] >> O[i] >> Y[i];
53             if (O[i] == ‘=‘) {
54                 if (merg(X[i],Y[i]))
55                     num--;
56             }
57         }
58         for (int i = 0;i < m; ++ i) if (O[i] != ‘=‘) {
59             int x = find(X[i]);
60             int y = find(Y[i]);
61             if (O[i] == ‘>‘) {
62                 G[x].push_back(y);
63                 son[y]++;
64             }
65             else {
66                 G[y].push_back(x);
67                 son[x]++;
68             }
69         }
70         queue<int> q;
71         for (int i = 0;i < n; ++ i)
72             if (son[i] == 0 && i == find(i))
73                 q.push(i);
74         int sin = 0;
75         while (!q.empty()) {
76             if (q.size() > 1) sin = 1;
77             int t = q.front();
78             q.pop();
79             --num;
80             for (int v = 0;v < G[t].size(); ++ v) {
81                 if (--son[G[t][v]] == 0)
82                     q.push(G[t][v]);
83             }
84         }
85         if (num > 0) cout << "CONFLICT" << endl;
86         else if (sin) cout << "UNCERTAIN" << endl;
87         else cout << "OK" << endl;
88     }
89     return 0;
90 }