拓扑排序

Rank of Tetris HDU - 1811

题目大意

 给出n个结点, 并给出这n个结点之间的关系, > , < ,= , 判断是否能够确定任意两者之间的顺序, 或者是否重复, 还是条件不足

分析

 需要基础知识: 拓扑排序与并查集,题目关键在于相等的情况, 相等的时候直接合并两个结点或集合, 然后对剩下的元素进行拓扑排序

参考代码

const int LEN_of_Node = 10000+100;
const int LEN_of_Edge = 20000+100;
int cnt ;
int N,M;
int num;
struct Edge
{
    int to,next;
};
Edge edge[LEN_of_Edge];
int head[LEN_of_Node];//邻接表存图
int F[LEN_of_Node];//并查集用
int in[LEN_of_Node];//记录入度
int a[LEN_of_Node];
char c[LEN_of_Node];
int b[LEN_of_Node];
void Init(void)//初始化函数
{
    cnt = 1;
    me(in);
    me(head);
    for(int i = 1; i <= N; ++i)
        F[i] = i;
}
int Find(int x)//并查集所用函数
{
    return x == F[x]?x:F[x] = Find(F[x]);
}
void Union(int aa,int bb)//并查集合并函数
{
    int x = Find(aa);
    int y = Find(bb);
    if(x!=y)
    {
        in[x] = -1;
        F[x] = y;
    }
}
void Add(int u,int v)//邻接表添加结点的函数
{
    edge[cnt].next = head[u];
    edge[cnt].to = v;
    head[u] = cnt++;
}
int Topo(void)//拓扑排序
{
    queue<int> que;//用队列记录
    for(int i = 1; i <= N; ++i)
    {
        if(in[i]==0&&i == Find(i))
        {
            que.push(i);
        }
    }
    int sign = 0;
    while(!que.empty())
    {
        if(que.size()>1)/*如果有两个结点, 表明无法确定这两个结点的顺序,应为他们肯定不是同rating的(并查集合并过了);*/
            sign = 1;
        int q = que.front();
        que.pop();
        in[q] = -1;//删除结点
        for(int i = head[q]; i; i  = edge[i].next)
        {
            int tmp = edge[i].to;
            in[tmp]--;
            if(in[tmp] == 0)//如果入度为零, 则加入队列
                que.push(tmp);
        }
    }
    for(int i = 1;i <= N;++i)
        if(in[i] != -1)//判断是否有没有处理的结点, 如果有,说明肯定有环
        return 2;
    if(sign)
        return 3;
    return 0;
}


int main(void)
{
    while(cin>>N>>M)
    {
            Init();
            for(int i = 1; i <= M; ++i)
            {
                scanf("%d %c %d",&a[i],&c[i],&b[i]);
                a[i]++;
                b[i]++;
                if(c[i]=='=')//如果相等就合并
                {
                    Union(a[i],b[i]);
                }
            }
            for(int i = 1; i <= M; ++i)
            {
                if(c[i]=='=')
                    continue;
                int aa = Find(a[i]);
                int bb = Find(b[i]);
                if(c[i]=='>')
                {
                    Add(aa,bb);
                    in[bb]++;
                }
                else
                {
                    Add(bb,aa);
                    in[aa]++;
                }
            }
            int sign = Topo();
            if(sign==0)
                printf("OK\n");
            else  if(sign==2)
                printf("CONFLICT\n");
            else if(sign==3)
                printf("UNCERTAIN\n");
    }
    return 0;
}

总结

此题就是将拓扑排序结合, 关键就是当队列中元素个数大于2时, 无法确定二者之间的关系