学步园

拓扑排序，加入了a=b；

将等于的多个点用并差集缩成一个点

#include<stdio.h>
#include<stack>
using namespace std;
int n,nm;
struct op
{
    int son;
    struct op *next;
}*p[10005];
int link[10005],ls[20005],ld[20005],f[10005];
int find(int a)
{
    if(a!=f[a])
        f[a]=find(f[a]);
    return f[a];
}
void insert(int a,int b)
{
    op *q=new op;
    q->son=b;
    q->next=p[a];
    p[a]=q;
}
int tuopusort()
{
    int flag=0,num=0;;
    stack<int>Q;
    for(int i=0;i<n;i++)
        if(link[i]==0&&find(i)==i)
            Q.push(i);
        while(!Q.empty())
        {
            if(Q.size()>1)flag=1;
            num++;
            int u=Q.top();
            Q.pop();
            for(op *j=p[u];j;j=j->next)
            {
                if(--link[j->son]==0)
                    Q.push(j->son);
            }
        }
        if(num!=nm)return 1;
        else if(flag==1)return 2;
        else       return 3;            
}
int main()
{
    int i,m,x,y;
    char ch[20005];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        nm=n;
        for(i=0;i<n;i++)
        {
            p[i]=NULL;
            f[i]=i;
            link[i]=0;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d %c %d",&ls[i],&ch[i],&ld[i]);
            if(ch[i]=='=')
            {
                x=find(ls[i]);y=find(ld[i]);
                if(x!=y)
                {
                    f[x]=y;nm--;
                }
            }
        }
        int flag=1;
        for(i=0;i<m;i++)
        {
            if(ch[i]=='=')continue;
            x=find(ls[i]);y=find(ld[i]);
            if(x==y){flag=0;break;}
            if(ch[i]=='>')
            {
                insert(x,y);
                link[y]++;
            }
            else 
            {
                insert(y,x);
                link[x]++;
            }
        }
        if(flag==0){puts("CONFLICT");continue;}
        int j=tuopusort();
              if(j==1)puts("CONFLICT");
            else if(j==2)puts("UNCERTAIN");
            else puts("OK");
    }
    return 0;
}