Rank of Tetris (并查集+拓普排序)

http://acm.hdu.edu.cn/showproblem.php?pid=1811
 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 #include <queue>
 5 #include <cstdio>
 6 #include <algorithm>
 7 using namespace std;
 8 const int N=10000+10;
 9 int n,m;
10 int p[N],in[N];
11 int arr[N],brr[N];
12 char op[N];
13 int finds(int x) {return x==p[x]? x:p[x]=finds(p[x]);}
14 int main()
15 {
16     int i,a,b,fa,fb,tn;
17     while(cin>>n>>m)
18     {
19         vector<int> v[N];tn=0;
20         queue<int> q;
21         char s[5];
22         memset(in,0,sizeof(in));
23         for(i=0;i<n;i++) p[i]=i;
24         for(i=0;i<m;i++)
25         {
26 
27             scanf("%d%s%d",&a,s,&b);
28             arr[i]=a;brr[i]=b;op[i]=s[0];
29             fa=finds(a);fb=finds(b);
30             if(s[0]=='=')//首先把相等的看成一个集合(一定要先做)
31             {
32                 if(fa!=fb) {p[fa]=fb;tn++;}
33             }
34         }
35         for(i=0;i<m;i++)//建立集合之间的关系(建图)
36         {
37             fa=finds(arr[i]);
38             fb=finds(brr[i]);
39             if(op[i]=='<')
40             {
41                 int temp=fa;
42                 fa=fb;fb=temp;
43             }
44             if(op[i]!='=')
45             {
46                 if( find( v[fa].begin(), v[fa].end(),fb)==v[fa].end())
47                 {
48                     v[fa].push_back(fb);
49                     in[fb]++;
50                 }
51             }
52         }
53         for(i=0;i<n;i++) if(in[i]==0&&p[i]==i)//所有的树根入队
54         {
55             q.push(i);
56         }
57         n-=tn;
58         int UNCERTAIN=0;
59         while(!q.empty())//拓普排序
60         {
61             if(q.size()>1) UNCERTAIN=1;//有多个根说明信息不完全
62             a=q.front();
63             q.pop();
64             n--;
65             for(i=0;i<v[a].size();i++)
66             {
67                 fa=v[a][i];
68                 if(--in[fa]==0)
69                 {
70                     q.push(fa);
71                 }
72             }
73         }
74         if(n>0) printf("CONFLICT\n");//n>0说明有环，冲突
75         else if(UNCERTAIN) printf("UNCERTAIN\n");
76         else printf("OK\n");
77     }
78     return 0;
79 }