HDU1811

 1 #include<iostream>
 2 #include<queue>
 3 #include<vector>
 4 #include<string.h>
 5 using namespace std;
 6 struct edge{
 7     int u,v;
 8     char c;
 9 }e[20010];
10 int f[10010],n,m,in[10010],uc,now,cnt,co,fam,tmp;
11 char c;
12 vector<int> a[10010];
13 
14 void ini(){
15     for (int i=0;i<n;i++) f[i]=i;
16     for (int i=0;i<n;i++) a[i].clear();
17     memset(e,0,sizeof e);
18     memset(in,0,sizeof in);
19     fam=cnt=uc=co=0;
20 }
21 
22 int getf(int u){
23     return f[u]==u?f[u]:f[u]=getf(f[u]);
24 }
25 
26 void merge(int u,int v){
27     f[getf(u)]=getf(v);
28 }
29 
30 void solve(){
31     while (cin>>n>>m){
32         ini();
33         for (int i=1;i<=m;i++){
34             scanf("%d %c %d",&e[i].u,&e[i].c,&e[i].v);
35             if (e[i].c==‘=‘) merge(e[i].u,e[i].v);
36         }
37         for (int i=1;i<=m;i++){
38             if (e[i].c==‘>‘){
39                 a[getf(e[i].u)].push_back(getf(e[i].v));
40                 in[getf(e[i].v)]++;
41             }
42             else if (e[i].c==‘<‘){
43                 a[getf(e[i].v)].push_back(getf(e[i].u));
44                 in[getf(e[i].u)]++;
45             }
46         }
47         queue<int> q;
48         for (int i=0;i<n;i++){
49             if (i==getf(i)){
50                 fam++;
51                 if (!in[i]) q.push(i);
52             }
53         }
54         if (q.size()>1) uc=1;
55         while (!q.empty()){
56             now=q.front();
57             q.pop();
58             tmp++;
59             for (int nx:a[now]){
60                 if (--in[nx]==0){
61                     q.push(nx);
62                     cnt++;
63                 }
64             }
65             if (cnt>1) uc=1;
66             cnt=0;
67         }
68         if (tmp<fam) co=1;
69         for (int i=0;i<n;i++){
70             if (in[i]){
71                 cout<<"CONFLICT"<<endl;
72                 co=1;
73                 break;
74             }
75         }
76         for (int i=1;i<=m;i++){
77             if (getf(e[i].u)==getf(e[i].v) && e[i].c!=‘=‘) co=1;
78         }
79         if (!co){
80             if (uc) cout<<"UNCERTAIN"<<endl;
81             else cout<<"OK"<<endl;
82         }
83         
84     }
85 }
86 
87 int main()
88 {
89     solve();
90     return 0;
91 }