1 /*  2 ACM1811 可以利用拓扑排序和并查集解决，主要方式是利用并查集在输入数据的时候将所有相等的点合并   3 然后将处理完的数据统一按照一个符号方向连接成有向线段，利用的是邻接矩阵；接下来把每条边都进行履历   4 如果出现conflict，那么就会在去除所有入度的时候无法找到新的零入度点，那么就会似的point无法减到零，  5 表示有conflict，如果出现uncertain，那么就会在一次寻找新的零入度点时能找到多个点，导致在队列中保存  6 多个数据 ；   7 */  8 #include<iostream>  9 #include<queue> 10 using namespace std; 11 class EDGE 12 { 13     public:  14     int from,to; 15     char sign; 16 }; 17 class WAY 18 { 19     public: 20     int from,to,next;  21 }; 22 class DEAL 23 { 24     public: 25     DEAL(int n,int m) 26     { 27         edge=new EDGE[m]; 28         way=new WAY[m]; 29         father=new int[n]; 30         head=new int[n]; 31         into=new int[n]; 32         for(int i=0;i<n;i++) 33         { 34         father[i]=i;head[i]=-1; 35         into[i]=0; 36         } 37         number=n; 38         point=n; 39         side=m; 40         count=0; 41         certain=true; 42         conflict=false; 43     } 44     ~DEAL() 45     { 46         delete []edge; 47         delete []father; 48         delete []way; 49         delete []head; 50         delete []into; 51     } 52     void Input() 53     { 54         for(int i=0;i<side;i++) 55         { 56             cin>>edge[i].from>>edge[i].sign>>edge[i].to; 57             if(edge[i].sign==‘=‘) 58             { 59             int fa=FindFather(edge[i].from); 60             int fb=FindFather(edge[i].to); 61                 Union(fa,fb); 62                 point--; 63             } 64         } 65     } 66     void Preprocess() 67     { 68         for(int i=0;i<side;i++) 69         { 70             if(edge[i].sign==‘=‘)continue; 71             int fa=FindFather(edge[i].from); 72             int fb=FindFather(edge[i].to); 73             if(fa==fb)conflict=true; 74             if(edge[i].sign==‘<‘) 75                 Merge(fb,fa); 76             else if(edge[i].sign==‘>‘) 77                 Merge(fa,fb); 78         } 79     } 80     void Toposort() 81     { 82         for(int i=0;i<number;i++) 83         { 84             if(into[i]==0&&father[i]==i)//是头节点  85                 q.push(i); 86         } 87         while(!q.empty()) 88         { 89             int l=q.front(); 90             q.pop(); 91             point--; 92             if(!q.empty())certain=false; 93             int v; 94             for(v=head[l];v!=-1;v=way[v].next) 95             { 96                 int u=way[v].to; 97                 into[u]--; 98                 if(!into[u])q.push(u); 99             }100         }101     }102     void Output()103     {104         if(point>0||conflict)105             cout<<"CONFLICT"<<endl;106         else if(!certain)cout<<"UNCERTAIN"<<endl;107         else cout<<"OK"<<endl;108     }109     int FindFather(int x)110     {111         if(x==father[x])return x;112         return father[x]=FindFather(father[x]);113     }114     void Union(int x,int y)115     {116         if(x!=y)father[y]=x;//后面跟着前面 117     }118     void Merge(int x,int y)119     {120         way[count].from=x;121         way[count].to=y;122         way[count].next=head[x];123         into[y]++;124         head[x]=count++;125     }126     private:127         queue<int>q;128         int number,side,point,count;129         EDGE *edge;130         WAY *way;131         int *father,*head,*into;132         bool certain,conflict;133 };134 int n,m;135 int main()136 {137     while(cin>>n>>m)138     {139         DEAL ob(n,m);140         ob.Input();141         ob.Preprocess();142         ob.Toposort();143         ob.Output();144     }145     return 0;146 }