Rank of Tetris(topsort)

http://acm.hdu.edu.cn/showproblem.php?pid=1811
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <vector>
 5 using namespace std;
 6 const int N=200010;
 7 vector<int>V[N];
 8 queue<int>q;
 9 char oper[N];
10 int in[N],f[N];
11 int a[N],b[N];
12 int n,m,sum;
13 void init()
14 {
15     sum = n;
16     while(!q.empty()) q.pop();
17     for (int i = 0; i <= n; i++)
18     {
19         f[i] = i;
20         in[i] = 0;
21         V[i].clear();
22     }
23 }
24 int Find(int x)
25 {
26     if(x!=f[x]) return f[x]=Find(f[x]);
27     return x;
28 }
29 int Merge(int x,int y)
30 {
31     x = Find(x);
32     y = Find(y);
33     if(x!=y)
34     {
35         f[y] = x;
36         return 1;
37     }
38     return 0;
39 }
40 void toposort()
41 {
42     int flag = 0;
43     for (int i = 0; i < n; i++)
44     {
45         if(in[i]==0&&Find(i)==i)
46             q.push(i);
47     }
48     while(!q.empty())
49     {
50         if (q.size()>1)flag = 1;
51         int u = q.front();
52         q.pop();
53         sum--;
54         for (int i = 0 ; i < V[u].size(); i++)
55         {
56             if(--in[V[u][i]]==0)
57                 q.push(V[u][i]);
58         }
59     }
60     if (sum > 0) printf("CONFLICT
");
61     else if (flag) printf("UNCERTAIN
");
62     else printf("OK
");
63 }
64 int main()
65 {
66     while(~scanf("%d%d",&n,&m))
67     {
68         init();
69         int u,v;
70         for (int i = 0; i < m; i++)
71         {
72             scanf("%d %c %d",&a[i],&oper[i],&b[i]);
73             if(oper[i]=='=')
74             {
75                 if(Merge(a[i],b[i]))
76                     sum--;
77             }
78         }
79         for (int i = 0; i < m; i++)
80         {
81             if(oper[i]=='=') continue;
82             u = Find(a[i]);
83             v = Find(b[i]);
84             if(oper[i]=='>')
85             {
86                 V[u].push_back(v);
87                 in[v]++;
88             }
89             if(oper[i]=='<')
90             {
91                 V[v].push_back(u);
92                 in[u]++;
93             }
94         }
95         toposort();
96     }
97     return 0;
98 }
View Code