题目描述

只说一个点：

从第一条边一直向后加入边，每个回合判断是否矛盾，是否能直接确定所有顺序
一旦满足上述两者其中一个，直接输出结果，跳出循环，结束

而m条边全部遍历完都无法确定时，才会输出无法确定

算法

(枚举+拓扑)

开始想到拓扑排序，但是感觉从前往后枚举一遍会超时，然后看了蓝书floyd的做法实现了一遍，感觉还不如直接拓扑

大致就是，

m次循环，每次加入一条边到图中，再跑一遍拓扑排序

• 排序后，排序数组不为n个，则表示有环，矛盾，跳出循环
• 排序后，排序数组为n个，但是在过程中，有2个或以上的点在队列中，表示拓扑序并不唯一，那么此时并不能确定所有点的顺序，因此进行下一次循环
• 排序后，排序数组为n个，且在过程中，队列中一直只有一个，拓扑序唯一，输出结果，跳出循环

这题如果是问你全局能不能构成有效排序，那么就可以二分再优化一下

时间复杂度

最差$O(m^2)$ (没细想，应该是这个)

比floyd快一点 （5ms和57ms)

C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e5+10;
const int N=25006,M=150000+100;
const int inf=0x3f3f3f3f;

int n,m,a[maxn],b[maxn],d[100][100];
string s;
int tot,head[100],nxt[maxn],ver[maxn],deg[100],t[100],ans[100],cnt;
bool f=1;

void add(int a,int b)  {
    ver[++tot]=b;
    nxt[tot]=head[a];
    head[a]=tot;
}

void init() {
    memset(deg,0,sizeof(deg));
    memset(t,0,sizeof(t));
    cnt=0;
    for(int i=0;i<n;i++)
        head[i]=0;
    tot=0;
}

void topsort() {
        //puts("-------------");
        queue<int>q;
        for(int i=0;i<n;i++) {
            if(deg[i]==0) q.push(i);
        }
        while(q.size()) {
            if(q.size()>1) f=0;
            int x=q.front();
            q.pop();
            ans[++cnt]=x;
        //    cout<<ans[cnt]<<endl;
            for(int i=head[x];i;i=nxt[i]) {
                int y=ver[i];
            //    cout<<y<<" "<<deg[y]<<endl;
                if(--deg[y]==0) q.push(y);
            }
        }
    //    puts("-------------");
}

int main() {
    while(~scanf("%d%d",&n,&m)&&(n&&m)) {

        init();

        for(int i=1;i<=m;i++) {
            cin>>s;
            a[i]=s[0]-'A';
            b[i]=s[2]-'A';
        }

        bool canb=1;

        for(int i=1;i<=m;i++) {
            cnt=0;
            add(a[i],b[i]);
            t[b[i]]++;
            for(int j=0;j<n;j++)
                deg[j]=t[j];
            f=1;
            topsort(); 
            if(cnt==n&&f) {
                printf("Sorted sequence determined after %d relations: ",i);
                for(int j=1;j<=cnt;j++) {
                    printf("%c",ans[j]+'A');
                }
                puts(".");
                canb=0;
                break;
            }  else if(cnt<n) {
                printf("Inconsistency found after %d relations.\n",i);
                canb=0;
                break;
            }
        }

        if(canb) puts("Sorted sequence cannot be determined.");

    }
    return 0;
}