题解 CF645D 【Robot Rapping Results Report】

EnochWenzhou · 2019-09-29 13:23:47 · 题解

这题有两种写法，一种是先二分答案是在第几条边，将小于此边的边都加入，跑一遍拓扑序列，假如在某一时间队列中的元素多于一个即表示这个图的拓扑序不只一种即为错误，反之可以排出名次。比较容易想到。O(nlogn)

这里再介绍另一种做法。加入几条边也等同于先把所有边加入后删除几条，那么只需在跑一遍拓扑序的时候记录能够求出这个点的拓扑序的最少边数为多少。记录dfn为拓扑序，id为最少边数。假如某一点x要更新y点时：假如dfn[x]+1>dfn[y]那么dfn[y]=dfn[x]+1,id[y]=x与y的边,假如dfn[x]+1==dfn[y]那么id[y]=max(id[y],x与y的边),即可。时间复杂度能够达到O(n)

O(n)做法：

#include<bits/stdc++.h>
#define LL long long
#define rint register int
#define M 100010
using namespace std;
int n,m,a1,b1,cnt,in[M],nt[M],to[M],ft[M],id[M],dfn[M],ID[M],mk[M],ans,F;
queue<int>q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a1,&b1);
        cnt++,id[cnt]=i,to[cnt]=b1,nt[cnt]=ft[a1],ft[a1]=cnt;in[b1]++;
    }
    for(int i=1;i<=n;i++)
        if(!in[i]){
            if(F){cout<<-1;return 0;}
            q.push(i),F=1;
        }
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=ft[x];i;i=nt[i]){
            int y=to[i];
            if(dfn[y]==dfn[x]+1)ID[y]=min(ID[y],id[i]);
            if(dfn[y]<dfn[x]+1)dfn[y]=dfn[x]+1,ID[y]=id[i];
            if(!(--in[y]))q.push(y);
        }
    }
    for(int i=1;i<=n;i++){if(mk[dfn[i]]){cout<<-1;return 0;}mk[dfn[i]]=1;}
    for(int i=1;i<=n;i++)ans=max(ans,ID[i]);
    cout<<ans;
    return 0;
}