1 #include <cstdio>  2 #include <cstring>  3 #include <stack>  4 #include <iostream>  5 using namespace std;  6   7 #define N 10005  8 char s[N<<1][3];  9 int fa[N] , first[N] , in[N] , k , cnt;//fa[i]保存的是i点处于的并查集号,cnt记录最后剩下的并查集数 10 bool vis[N];//判断对应下标的集合是否会进入最后生成的图中 11 struct Edge{ 12     int y,next; 13 }e[N<<1]; 14  15 void add_edge(int x,int y) 16 { 17     in[y]++; 18     e[k].y = y , e[k].next=first[x]; 19     first[x] = k++; 20 } 21  22 void init(int n) 23 { 24  25     k=0; 26     memset(first , -1 , sizeof(first)); 27     memset(in,0,sizeof(in)); 28     for(int i=0;i<n;i++) 29         fa[i] = i , vis[i] = true; 30 } 31  32 int find_fa(int x) 33 { 34     while(x!=fa[x]) 35         x=fa[x]; 36     return x; 37 } 38  39 void Union(int a , int b) 40 { 41     int fa1_set = find_fa(a); 42     int fa2_set = find_fa(b); 43     if(fa1_set != fa2_set) 44     { 45         fa[fa2_set] = fa1_set , cnt--; 46         vis[fa2_set] = false; //fa2_set集合被合并，所以最后不会进入图中，所以将其舍去 47     } 48 } 49  50 int tuopu(int n) 51 { 52     stack<int> s; 53     for(int i = 0 ; i<n ; i++){ 54         if(vis[i] && !in[i]) s.push(i); 55     } 56     int flag = 1; 57     for(int i=0 ; i<cnt ; i++){ 58         if(s.empty()) return -1; 59         if(s.size() > 1) flag = 0; 60         int u = s.top(); 61         s.pop(); 62         for(int j=first[u] ; j!=-1 ; j=e[j].next){ 63             int v = e[j].y; 64             in[v]--; 65             if(!in[v]){ 66                 s.push(v); 67             } 68         } 69     } 70     if(!flag) return 0; 71     return 1; 72 } 73  74 int main() 75 { 76    // freopen("a.in" , "rb" ,stdin); 77     int n , m , a[N] , b[N]; 78     while(scanf("%d%d",&n,&m)!=EOF) 79     { 80         init(n); 81         cnt = n; 82  83         for(int i=0;i<m;i++){ 84             scanf("%d%s%d",&a[i],s[i],&b[i]); 85             if(s[i][0] == ‘=‘){ 86                 Union(a[i],b[i]); 87             } 88         } 89         //cout<<"cnt: "<<cnt<<endl; 90         for(int i = 0 ; i<m ; i++){ 91             int fa1 = find_fa(a[i]); 92             int fa2 = find_fa(b[i]); 93             if(s[i][0] == ‘<‘){ 94                 add_edge(fa1 , fa2); 95             } 96             else if(s[i][0] == ‘>‘){ 97                 add_edge(fa2 , fa1); 98             } 99         }100         int flag = tuopu(n);101         if(flag == 1) puts("OK");102         if(flag == -1) puts("CONFLICT");103         if(flag == 0) puts("UNCERTAIN");104     }105     return 0;106 }