[POJ1094] Sorting It All Out

link

题目大意

给出$m$个不等式关系，问可以从第几个开始确定所有之间的大小关系。若无解请输出是无法确定还是与已知矛盾。

试题分析

这题是真的是坑啊，尽然放在$floyd$传到闭包上面，还用二分，是真的强啊。

其实一下子就会知道其实这是一道拓扑排序的题，所以当我们每次输入问一条边时，我们就去拓扑判断是否会形成环，条件是否充足，与顺序，然后就记得分类讨论即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

queue<int> que;

int n,m,in[],d[][],find1,k[];

char out[];

char str[];

int topu(){

    while(!que.empty()) que.pop();

    for(int i=;i<=;i++) k[i]=in[i];

    for(int i=;i<=n;i++){if(!in[i]) que.push(i);}

    int sx=,num=;

    while(!que.empty()){

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

        int xx=que.front();que.pop();

        out[++num]=xx+'A'-;

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

            if(d[xx][i]){

                k[i]--;

                if(k[i]==) que.push(i);

            }

        }

    }

    if(num!=n) return ;

    if(sx==) return -;

    return ;

}

int query,step;

int main(){

//    freopen("7.in","r",stdin);

    while(){

        memset(in,,sizeof(in)),find1=,query=,step=;

        memset(d,,sizeof(d));

        n=read(),m=read();

        if(!n&&!m) return ;

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

            cin>>(str+);

            int u=str[]-'A'+,v=str[]-'A'+;

            if(str[]=='>') swap(u,v);

            if(find1||query) continue;

            if(d[v][u]){find1=;printf("Inconsistency found after %d relations.",i);continue;}

            if(!d[u][v]){

                d[u][v]=;

                in[v]++;

            }

            int pd=topu();

            if(pd==){query=;step=i;continue;}

            if(pd==){printf("Inconsistency found after %d relations.",i);find1=;continue;}

        }

        if(query&&find1==){

            printf("Sorted sequence determined after %d relations: ",step);

            for(int i=;i<=n;i++) cout<<out[i];

            printf(".");

        }

        if(find1==&&query==) printf("Sorted sequence cannot be determined.");

        printf("\n");

    }

}