123

it2022-05-05  123

#include<bits/stdc++.h> using namespace std; vector<pair<int,int> > vec[10005]; pair<int,int> p; int pre[10005]; queue<int> que; int B[10005]; int C[10005]; int n,m; struct stu { int x; char ch[3]; int y; }A[20005]; int find(int x) { int r=x; while(pre[r]!=r) r=pre[r]; int i=x,j; while(i!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } void join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) pre[fx]=fy; } int main() { while(~scanf("%d %d",&n,&m)) { memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); memset(C,0,sizeof(C)); memset(pre,0,sizeof(pre)); for(int i=0;i<10005;i++) vec[i].clear(); for(int i=0;i<=n;i++) pre[i]=i; for(int i=0;i<m;i++) { scanf("%d%s%d",&A[i].x,&A[i].ch,&A[i].y); if(A[i].ch[0]=='=') join(A[i].x,A[i].y); } for(int i=0;i<m;i++) { if(A[i].ch[0]!='=') { int a1=find(A[i].x); int a2=find(A[i].y); if(A[i].ch[0]=='>') { vec[a1].push_back(make_pair(a2,1)); B[a2]++; } else { vec[a2].push_back(make_pair(a1,1)); B[a1]++; } } } int cnt1=0,cnt2=0; for(int i=0;i<n;i++) { int aa=find(i); if(B[aa]==0&&C[aa]==0) { que.push(aa); C[aa]=1; } } if(que.size()>1) cnt1=1; if(que.size()==0) cnt2=1; while(!que.empty()) { int a1=que.front(); que.pop(); for(int i=0;i<vec[a1].size();i++) { p=vec[a1][i]; if(p.second==1) { B[p.first]--; if(B[p.first]==0) que.push(p.first); } } if(que.size()>1) cnt1=1; } for(int i=0;i<n;i++) { if(B[i]!=0) { cnt2=1; break; } } if(n==1&&m==0) printf("OK\n"); else if(m==0) printf("UNCERTAIN\n"); else if(cnt1==0&&cnt2==0) printf("OK\n"); else if(cnt2==1) printf("CONFLICT\n"); else printf("UNCERTAIN\n"); } return 0; }

 


最新回复(0)