Rank of Tetris HDU - 1811【拓扑排序+并查集】

#include <bits/stdc++.h>
//基本思路：先用并查集处理 = 关系，归为一个集合，每次对该集合内的元素进行操作时，只对父亲操作即可。
//然后利用拓扑排序处理级别关系
using namespace std;
const int N=1e4+5;
int pre[N],degree[N],a[2*N],b[2*N];
char c[2*N];
vector<int>pic[N];
queue<int>que;
int Find(int x)
{
    if(x!=pre[x])
        return pre[x]=Find(pre[x]);
    else
        return x;
}
void solve(int rest,int n)
{
    bool flag=0;
    while(!que.empty())
        que.pop();
    for(int i=0;i<n;i++)
    {
        if(degree[i]==0&&Find(i)==i)
            que.push(i),rest--;
    }
    while(!que.empty())
    {
        if(que.size()>1)
            flag=1;
        int now=que.front();
        que.pop();
        for(int i=0;i<pic[now].size();i++)
        {
            int tmp=pic[now][i];
            if(--degree[tmp]==0)
            {
                que.push(tmp);
                rest--;
            }
        }
    }
    if(rest>0)
        printf("CONFLICT\n");
    else
    {
        if(flag)
            printf("UNCERTAIN\n");
        else
            printf("OK\n");
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<=n;i++)
        {
            pre[i]=i;
            pic[i].clear();
        }
        memset(degree,0,sizeof(degree));
        int res=n;
        for(int i=1;i<=m;i++)
        {
            scanf("%d %c %d",&a[i],&c[i],&b[i]);
            if(c[i]=='=')
            {
                int pa=Find(a[i]);
                int pb=Find(b[i]);
                if(pa!=pb)
                {
                    pre[pa]=pb;
                    res--;//发现新的不适用该集合的元素，res--
                }
            }
        }
        for(int i=1;i<=m;i++)
        {
            int pa=Find(a[i]);
            int pb=Find(b[i]);
            if(c[i]=='>')
            {
                pic[pa].push_back(pb);
                degree[pb]++;
            }
            else if(c[i]=='<')
            {
                pic[pb].push_back(pa);
                degree[pa]++;
            }
        }
        solve(res,n);
    }
    return 0;
}