hdu 1181(并查集+拓扑排序）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1811

思路：先处理‘=‘，全部合并为同一个节点，然后在拓扑排序就可以了。。。

拓扑排序知识：

*如果一次入队入度为零的点大于1则说明拓扑排序序列不唯一
*如果排序的总个数小于给定的个数,则说明存在回路

View Code

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<vector>
  6 #include<queue>
  7 using namespace std;
  8 const int MAXN=10000+10;
  9 int parent[MAXN];
 10 int In[MAXN];
 11 vector<int>vet[MAXN];
 12 int n,m,num;
 13 struct Edge {
 14     int u,v;
 15     char ch;
 16 }edge[MAXN];
 17 
 18 
 19 void Initiate(){
 20     for(int i=0;i<n;i++){
 21         parent[i]=-1;
 22         vet[i].clear();
 23         In[i]=0;
 24     }
 25 }
 26 
 27 int Find(int x){
 28     int s;
 29     for(s=x;parent[s]>=0;s=parent[s]);
 30     while(s!=x){
 31         int tmp=parent[x];
 32         parent[x]=s;
 33         x=tmp;
 34     }
 35     return s;
 36 }
 37 
 38 void Union(int R1,int R2){
 39     int r1=Find(R1);
 40     int r2=Find(R2);
 41     if(r1!=r2){
 42         parent[r2]=r1;
 43     }
 44 }
 45 
 46 
 47 int main(){
 48     while(~scanf("%d%d",&n,&m)){
 49         Initiate();
 50         num=n;//总共要进行拓扑排序的n个点
 51         for(int i=0;i<m;i++){
 52             int u,v;
 53             scanf("%d %c %d",&edge[i].u,&edge[i].ch,&edge[i].v);
 54             if(edge[i].ch=='='){
 55                 Union(edge[i].u,edge[i].v);
 56                 num--;
 57             }
 58         }
 59         bool flag=true;
 60         for(int i=0;i<m;i++){
 61             if(edge[i].ch=='=')
 62                 continue;
 63             int r1=Find(edge[i].u);
 64             int r2=Find(edge[i].v);
 65             //如果找到了相等的，说明矛盾；
 66             if(r1==r2){
 67                 flag=false;
 68                 break;
 69             }
 70             if(edge[i].ch=='>'){
 71                 vet[r1].push_back(r2);
 72                 In[r2]++;
 73             }else if(edge[i].ch=='<'){
 74                 vet[r2].push_back(r1);
 75                 In[r1]++;
 76             }
 77         }
 78         if(!flag){
 79             puts("CONFLICT");
 80         }else {
 81             queue<int>Q;
 82             for(int i=0;i<n;i++){
 83                 if(In[i]==0&&Find(i)==i){
 84                     Q.push(i);
 85                 }
 86             }
 87             while(!Q.empty()){
 88                 //如果同一层有多个点，说明存在多个拓扑排序
 89                 if(Q.size()>1){
 90                     flag=false;
 91                 }
 92                 num--;
 93                 int u=Q.front();
 94                 Q.pop();
 95                 for(int i=0;i<vet[u].size();i++){
 96                     //只有入度为1的才可入队列
 97                     if(--In[vet[u][i]]==0){
 98                         Q.push(vet[u][i]);
 99                     }
100                 }
101             }
102             //说明存在环，矛盾
103             if(num>0){
104                 puts("CONFLICT");
105             }else if(!flag){
106                 puts("UNCERTAIN");
107             }else 
108                 puts("OK");
109         }
110     }
111     return 0;
112 }