题意:
思路:topo+并查集
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
vector<int > web[];
int p[],n,m,sum,f[],A[],B[];
char C[];
bool ok;
int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
void order(){
queue<int> q;
for ( int i = ; i < n ; ++i)
if ( f[i] == && find(i) == i )
q.push(i);
while(!q.empty()){
if ( q.size() > ) ok=true;///否则说明信息不完全
int cur = q.front();
q.pop();
sum--;
for(int i = ; i < web[cur].size() ; ++i)
{
if(--f[web[cur][i]]==)
q.push(web[cur][i]);
}
}
return ;
}
int main(){
while (scanf("%d %d",&n,&m) != EOF){
ok = false ;sum = n;
for (int i = ;i <= n;++i){
p[i] = i;
web[i].clear();
f[i] = ;
}
for (int i = ;i < m; ++i){
scanf("%d %c %d",&A[i],&C[i],&B[i]);
int x = find(A[i]),y = find(B[i]);
if (C[i] == '='){
if (x != y){
p[y] = x;
sum--;
}
}
}
for (int i = ;i < m;++i){
if (C[i] == '=') continue;
int x = find(A[i]);
int y = find(B[i]);
if (C[i] == '>'){
web[x].push_back(y);
f[y]++;
}
else {
web[y].push_back(x);
f[x]++;
}
}
order();
if (sum > ) printf("CONFLICT\n");
else if (ok) printf("UNCERTAIN\n");
else printf("OK\n");
}
return ;
}