hdu1811 拓扑排序+并查集缩点

/*
给定两个点之间的三种关系 = < >
如果是=就将两点放到同一个集合里进行缩点

离线处理所有关系，先用并查集将等于关系缩成一个点

*/

#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<<];

int n,m,head[maxn],tot;

void init(){

    memset(head,-,sizeof head);

    tot=;

}

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]==-?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,-,sizeof f);

        memset(in,,sizeof in);

        for(int i=;i<=m;i++)

            cin>>q[i].u>>q[i].ch>>q[i].v;

        for(int i=;i<=m;i++)

            if(q[i].ch=='=')

                bing(q[i].u,q[i].v);

        for(int i=;i<=m;i++)

            q[i].u=find(q[i].u),q[i].v=find(q[i].v);

        for(int i=;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=,cnt=;

        queue<int>que;

        for(int i=;i<n;i++)

            if(f[i]==-)cnt++;

        for(int i=;i<n;i++)

            if(f[i]==- && in[i]==)

                que.push(i);

        if(que.size()>)flag=;

        while(!que.empty()){

            int u=que.front();

            que.pop();

            cnt--;

            for(int i=head[u];i!=-;i=edge[i].nxt){

                int v=edge[i].to;

                in[v]--;

                if(in[v]==)

                    que.push(v);

            }

            if(que.size()>)flag=;

        }

        if(cnt>)puts("CONFLICT");

        else if(flag==)puts("UNCERTAIN");

        else puts("OK");

    }

}