hdu 1811 Rank of Tetris

http://acm.hdu.edu.cn/showproblem.php?pid=1811
拓扑排序和并差集
  1 #include <cstdio>
  2 #include <queue>
  3 #include <vector>
  4 #include <cstring>
  5 #include <algorithm>
  6 #define maxn 10010
  7 using namespace std;
  8 int n,m,c;
  9 int f[maxn],in[maxn];
 10 vector<int>g[maxn];
 11 struct node
 12 {
 13     int x,y;
 14     char ch;
 15 }p[maxn*5];
 16 void inti()
 17 {
 18     for(int i=0; i<=n; i++)
 19     {
 20         f[i]=i; in[i]=0;
 21         g[i].clear();
 22     }
 23 }
 24 
 25 int find1(int x)
 26 {
 27     if(x==f[x]) return x;
 28     return f[x]=find1(f[x]);
 29 }
 30 
 31 void merge1(int a,int b)
 32 {
 33     int fa=find1(a);
 34     int fb=find1(b);
 35     if(fa!=fb)
 36     {
 37         f[fb]=fa;
 38     }
 39 }
 40 
 41 int  topp()
 42 {
 43     int flag=0;
 44     queue<int>q;
 45     for(int i=0; i<n; i++)
 46     {
 47         if(!in[i]&&find1(i)==i) q.push(i);
 48     }
 49     int cnt=0;
 50     while(!q.empty())
 51     {
 52         if(q.size()>=2) flag=-1;
 53         int x=q.front(); q.pop();
 54         cnt++;
 55         for(int i=0; i<(int)g[x].size(); i++)
 56         {
 57             if((--in[g[x][i]])==0) q.push(g[x][i]);
 58         }
 59     }
 60     if(cnt<c) return 1;
 61     return flag;
 62 }
 63 int main()
 64 {
 65     while(~scanf("%d%d",&n,&m))
 66     {
 67         inti();
 68         c=n;
 69         for(int i=0; i<m; i++)
 70         {
 71             scanf("%d%*c%c%*c%d",&p[i].x,&p[i].ch,&p[i].y);
 72             if(p[i].ch=='=')
 73             {
 74                 merge1(p[i].x,p[i].y); c--;
 75             }
 76         }
 77         bool flag=false;
 78         for(int i=0; i<m; i++)
 79         {
 80             if(p[i].ch=='=')
 81             {
 82                 continue;
 83             }
 84             int x1=find1(p[i].x); int y1=find1(p[i].y);
 85             if(x1==y1) flag=true;
 86             if(p[i].ch=='<')
 87             {
 88                 if(find(g[x1].begin(),g[x1].end(),y1)==g[x1].end())
 89                 {
 90                     g[x1].push_back(y1);
 91                     in[y1]++;
 92                 }
 93             }
 94             else if(p[i].ch=='>')
 95             {
 96                 if(find(g[y1].begin(),g[y1].end(),x1)==g[y1].end())
 97                 {
 98                     g[y1].push_back(x1);
 99                     in[x1]++;
100                 }
101             }
102         }
103         bool flag1=false;
104         if(!flag)
105         {
106             int cc=topp();
107             if(cc==1) flag=true;
108             else if(cc==-1) flag1=true;
109         }
110         if(flag)
111         {
112             printf("CONFLICT
");
113         }
114         else if(flag1)
115         {
116             printf("UNCERTAIN
");
117         }
118         else printf("OK
");
119     }
120     return 0;
121 }
View Code