hdu 1811 Rank of Tetris

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <math.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <ctype.h>
  7 #include <iomanip>
  8 #include <queue>
  9 #include <stdlib.h>
 10 using namespace std;
 11 
 12 #define MAX 100010
 13 
 14 int N,M;
 15 int sum;
 16 int x[MAX],y[MAX];
 17 char pr[MAX];
 18 int root[MAX];
 19 vector<int> v[MAX];
 20 int du[MAX];
 21 
 22 //找到根
 23 int find_root(int a)
 24 {
 25     if(root[a] == a)return a;
 26     return root[a] = find_root(root[a]);
 27 }
 28 
 29 //合并两个集合
 30 int Union(int a,int b)
 31 {
 32     a = find_root(a);
 33     b = find_root(b);
 34     if(a==b)return 0;
 35     root[b]=a;
 36     return 1;
 37 }
 38 //初始化
 39 void init()
 40 {
 41     for(int i=0;i<=N;i++)
 42     {
 43         root[i]=i;
 44         v[i].clear();
 45         du[i]=0;
 46     }
 47     memset(du, 0, sizeof(du)); 
 48 }
 49 //拓扑排序
 50 void topu()
 51 {
 52     bool U=false;
 53     queue<int> q;
 54     for(int i=0;i<N;i++){
 55         if(du[i]==0 && find_root(i)==i)
 56             q.push(i);
 57     }
 58     while(!q.empty()){
 59         if(q.size()>1)
 60             U=true;
 61         int cur = q.front();
 62         q.pop();
 63         sum--;
 64         for(int i=0;i<v[cur].size();i++)
 65         {
 66             if(--du[v[cur][i]]==0)
 67             q.push(v[cur][i]);
 68         }
 69     }
 70     if(sum>0)printf("CONFLICT\n");
 71     else if(U)printf("UNCERTAIN\n");
 72     else printf("OK\n");
 73 }
 74 
 75 int main()
 76 {
 77     int a,b;
 78     while(~scanf("%d %d",&N,&M)){
 79         init();
 80         sum=N;
 81         for(int i=0;i<M;i++){
 82             scanf("%d %c %d",&x[i],&pr[i],&y[i]);
 83             if(pr[i]==‘=‘){
 84                 if(Union(x[i],y[i]))
 85                     sum--;
 86             }
 87         }
 88         for(int i=0;i<M;i++){
 89             if(pr[i]==‘=‘)   
 90                 continue;
 91             a=find_root(x[i]);
 92             b=find_root(y[i]);
 93             if(pr[i]==‘>‘){
 94                 v[a].push_back(b);
 95                 du[b]++;
 96             }
 97             else{
 98                 v[b].push_back(a);
 99                 du[a]++;
100             }
101         }
102         topu();
103     }
104 }