/*给定两个点之间的三种关系 = < >如果是=就将两点放到同一个集合里进行缩点
离线处理所有关系，先用并查集将等于关系缩成一个点
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 20005
struct Query{
int u,v;
char ch;}q[maxn];
struct Edge{
int to,nxt;}edge[maxn<<
1];
int n,m,head[maxn],tot;
void init(){
memset(head,-
1,
sizeof head);
tot=
0;
}
void addedge(
int u,
int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++
;
}
/*并查集*/
int f[maxn];
int find(
int x){
return f[x]==-
1?x:f[x]=
find(f[x]);
}
void bing(
int a,
int b){
int t1=
find(a);
int t2=
find(b);
if(t1!=t2)f[t1]=
t2;
}
int in[maxn];
int main(){
while(cin>>n>>
m){
init();
memset(f,-
1,
sizeof f);
memset(in,
0,
sizeof in);
for(
int i=
1;i<=m;i++
)
cin>>q[i].u>>q[i].ch>>
q[i].v;
for(
int i=
1;i<=m;i++
)
if(q[i].ch==
'=')
bing(q[i].u,q[i].v);
for(
int i=
1;i<=m;i++
)
q[i].u=find(q[i].u),q[i].v=
find(q[i].v);
for(
int i=
1;i<=m;i++
){
if(q[i].ch==
'=')
continue;
if(q[i].ch==
'<'){
in[q[i].u]++
;
addedge(q[i].v,q[i].u);
}
if(q[i].ch==
'>'){
in[q[i].v]++
;
addedge(q[i].u,q[i].v);
}
}
int flag=
0,cnt=
0;
queue<
int>
que;
for(
int i=
0;i<n;i++
)
if(f[i]==-
1)cnt++
;
for(
int i=
0;i<n;i++
)
if(f[i]==-
1 &&
in[i]==
0)
que.push(i);
if(que.size()>
1)flag=
1;
while(!
que.empty()){
int u=
que.front();
que.pop();
cnt--
;
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
in[v]--
;
if(
in[v]==
0)
que.push(v);
}
if(que.size()>
1)flag=
1;
}
if(cnt>
0)puts(
"CONFLICT");
else if(flag==
1)puts(
"UNCERTAIN");
else puts(
"OK");
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10449143.html
