BNUOJ 5966 Rank of Tetris

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 20010;
18 int A[maxn],B[maxn],uf[maxn],n,m;
19 char op[maxn][5];
20 vector<int>next[10010];
21 int pre[10010],sum;
22 int Find(int x){
23     if(x != uf[x]) uf[x] = Find(uf[x]);
24     return uf[x];
25 }
26 void top_sort(){
27     bool uncertain = false;
28     queue<int>q;
29     for(int i = 0; i < n; i++){
30         if(!pre[i] && Find(i) == i) q.push(i);
31     }
32     while(!q.empty()){
33         if(q.size() > 1) uncertain = true;
34         int now = q.front();
35         q.pop();
36         sum--;
37         for(int i = 0; i < next[now].size(); i++){
38             if(--pre[next[now][i]] == 0) q.push(next[now][i]);
39         }
40     }
41     if(sum > 0) puts("CONFLICT");
42     else if(uncertain) puts("UNCERTAIN");
43     else puts("OK");
44 }
45 int main() {
46     int i,j;
47     while(~scanf("%d %d", &n,&m)){
48         for(i = 0; i <= n; i++){
49             uf[i] = i;
50             next[i].clear();
51             pre[i] = 0;
52         }
53         sum = n;
54         for(i = 0; i < m; i++){
55             scanf("%d %s %d",A+i,op[i],B+i);
56             int tx = Find(A[i]);
57             int ty = Find(B[i]);
58             if(op[i][0] == ‘=‘){
59                 if(tx != ty) {uf[tx] = ty;sum--;}
60             }
61         }
62         for(i = 0; i < m; i++){
63             if(op[i][0] == ‘=‘) continue;
64             int tx = Find(A[i]);
65             int ty = Find(B[i]);
66             if(op[i][0] == ‘>‘){
67                 pre[ty]++;
68                 next[tx].push_back(ty);
69             }else if(op[i][0] == ‘<‘){
70                 pre[tx]++;
71                 next[ty].push_back(tx);
72             }
73         }
74         top_sort();
75     }
76     return 0;
77 }