题目大意：

有N个元素，序号从0到n-1

有M条信息，每条信息为

u c v

表示序号为u的元素和序号为v的元素的大小关系

c为>,<,=

问你根据给定的信息是否能够确定这n个元素的排序

如果存在冲突，输出conflict

如果不存在冲突但无法确定，那么输出uncertain

如果可以确定输出ok

 

解法：

1.首先我们考虑不存在=，所有c都是>或<的情况

我们将每个信息都视为一条用较大的元素到较小元素的有向边

如果这个图有确定且唯一的拓扑序，那么就是可以确定顺序的

那么对这个图做拓扑排序

冲突是指这个图中存在环，那么也就无法完成拓扑排序

不确定是指bfs时拆下一个点的同时会将2个或更多的点加入队列

2.对于=的情况，我们将这两个元素用并查集合并即可

#include
     
      #include
      
        #include
       
        using namespace std;const int N=10005;struct E{    int v,n;}e[N<<1];int anc[N],tu[N<<1],tv[N<<1],fir[N],s,d[N];queue
        
         dl;int fi(int a){    int b=a;    while(anc[b]!=b) b=anc[b];    while(anc[a]!=b){        int t=anc[a];        anc[a]=b;        a=t;    }    return b;}void add(int u,int v){    ++d[v];    e[++s].v=v;    e[s].n=fir[u];    fir[u]=s;}int main(){    //freopen("a.in","r",stdin);     int n,m,u,v;    while(scanf("%d%d",&n,&m)==2){        int sl=0,pd=1;s=0;        memset(d,0,sizeof(d));        memset(fir,0,sizeof(fir));        memset(e,0,sizeof(e));        for(int i=1;i<=n;++i) anc[i]=i;        while(m--){            char c;            scanf("%d %c %d",&u,&c,&v);            ++u,++v;            if(c=='='){                anc[fi(u)]=fi(v);                continue;            }            else if(c=='<') swap(u,v);            tu[++sl]=u;            tv[sl]=v;        }        for(int i=1;i<=sl;++i){            int fu=fi(tu[i]),fv=fi(tv[i]);            if(fu!=fv) add(fu,fv);            else pd=0;        }        if(pd){            sl=0;            for(int i=1;i<=n;++i)                if(anc[i]==i&&!d[i]) dl.push(i);            while(!dl.empty()){                if(dl.size()>1) sl=1;                u=dl.front();dl.pop();                for(int i=fir[u];i;i=e[i].n){                        v=e[i].v;                        --d[v];                        if(!d[v]) dl.push(v);                    }            }            for(int i=1;i<=n;++i)                if(d[i]) pd=0;        }        if(!pd) printf("CONFLICT\n");        else if(sl) printf("UNCERTAIN\n");        else printf("OK\n");    }    return 0;}