henrytb 的博客

henrytb 的博客

浅谈拓扑排序

posted on 2018-07-31 15:55:30 | under 洛谷日爆 |

大前言

拓扑排序是一种图论算法,对OI很有用,实现也比较简单。

前言

机房里,大家都在互相进行机房惨案(盗用别人账号发表令人不快的言论,以下简称基惨)。

老师想找到这次是谁引发的这次基惨。

如图,1和2基惨了3,3为了报仇基惨了4,4为了报仇基惨了5和6,6为了报仇基惨了7和8.

正题

基惨的罪魁祸首肯定是没有被基惨的,所以他们的入度为 $0$ .

在本图中,1和2入度为 $0$ ,所以1和2是本次基惨的罪魁祸首。

于是,老师把他们揪去写检讨了。

现在,老师又想知道,谁是下一批基惨别人的人。

看图,发现这个人的是3.

那么,3有什么性质呢?

我们发现,1和2被老师揪去写检讨了,所以图中没有了1和2.

于是,基惨图变成了这样:

发现,第二轮基惨的3的入度也变成了 $0$ !

于是,老师高兴坏了,赶快把3也揪出去写检讨。

现在4入度为 $0$ 了。

就这样以此类推......

具体实现

通过上面一个故事,我们知道了拓扑排序的方法。

具体的实现是这样的:

首先,开一个队列,将入度为 $0$ 的点放进去。

然后依次删掉队列里的点,更新入度。

如果有入度为 $0$ 的点就把它再放进队列里。

直到队列为空为止。

反例

你们有没有想一想,拓扑排序有没有反例呢?

答案是肯定的。

我们考虑这样一个图:

发现无法找到是谁先开始基惨的。

因为这个图有

所以, $\color{red}\text{拓扑排序仅对有向无环图有效}$ 。

例题

建议做一做P2712 摄像头

题目大意

有 $n$ 个点,可以删去入度为 $0$ 的点(包括删完一个点后入度变为 $0$ 的点),问剩下几个点?

题解

这题就是一道典型的拓扑排序。

一轮一轮模拟即可。

具体步骤见注释。

code:

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,x,ma[N][N],k,du[N],q[10*N],l=1,r,maxx;
bool used[N];//记录有没有这个点
int main(){
//-----------读入------------
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&m);
        used[x]=true;
        for(int j=1;j<=m;j++){
            scanf("%d",&k);
            ma[x][k]=1;
            du[k]++;
        }
        maxx=max(maxx,x);//最大的点编号
    }
//-----------拓扑排序------------------
    for(int i=0;i<=maxx;i++)
        if(du[i]==0&&used[i])q[++r]=i;//将入度为0的点放入队列
    int ans=0;//记录删了多少个点
    while(ans<n){
        if(l>r){//不可再删
            printf("%d",n-ans);
            return 0;
        }
        int cmd=q[l++];//删点
        for(int i=0;i<=maxx;i++){
            if(ma[cmd][i]&&used[i]){
                du[i]--;//处理与被删的点相邻的点的入度
                if(du[i]==0&&used[i])q[++r]=i;//如果此点更新后入度为0,将此点放入队列
            }
        }
        ans++;//更新已删的点的个数
    }
    if(ans==n)printf("YES");
    return 0;
}

友情提示:请大家不要抄!仅仅抄而不懂里面的含义是没用的!

综合例题

P3627 [APIO2009]抢掠计划

拓扑排序经常和各种其他算法一起配合使用。

这题用到了求强连通分量、缩点、拓扑排序以及DP求最长路。

题目大意

一个人从 $1$ 出发,经过一些银行,最后到其中几个指定的酒吧,求最多抢多少钱。

题解

先缩强连通分量,然后拓扑排序,求最长路即可。

我在这里求强连通分量的方法是 $Kosaraju$ ,因为我不会 $Tarjan$ (我太弱了)。

code:

#include <bits/stdc++.h>
using namespace std;
const int M=1000005,INF=2e9;
bool used[M],bar[M];
int tot,tot2,tot3,
target[M],last[M],prev1[M],
target2[M],last2[M],prev2[M],
target3[M],last3[M],prev3[M],
s[M],n,m,p[M],sum[M],fa[M],u[M],
ans,v[M],d[M],a[M],b[M],h,t,q[M],f[M],start,barg;
void add(int a,int b){
    target[++tot]=b;
    prev1[tot]=last[a];
    last[a]=tot;
}
void add2(int a,int b){
    target2[++tot2]=b;
    prev2[tot2]=last2[a];
    last2[a]=tot2;
}
void add3(int a,int b){
    target3[++tot3]=b;
    prev3[tot3]=last3[a];
    last3[a]=tot3;
    d[b]++;
}
void dfs1(int u){
    used[u]=true;
    int ptr=last[u];
    while(ptr){
        int k=target[ptr];
        if(!used[k])dfs1(k);
        ptr=prev1[ptr];
    }
    s[++s[0]]=u;
}
void dfs2(int u,int index){
    bar[index]|=bar[u];
    p[index]=min(p[index],u);
    sum[index]+=v[u];
    used[u]=true;
    fa[u]=index;
    int ptr=last2[u];
    while(ptr){
        int k=target2[ptr];
        if(!used[k])dfs2(k,index);
        ptr=prev2[ptr];
    }
    return;
}
int main(){
    //--------------输入---------------
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a[i],&b[i]);
        add(a[i],b[i]);
        add2(b[i],a[i]);
    }
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    scanf("%d%d",&start,&barg);
    for(int i=1;i<=barg;i++){
        int a;
        scanf("%d",&a);
        bar[a]=true;
    }
    //------------求强连通分量------------
    memset(used,false,sizeof(used));
    for(int i=1;i<=n;i++)if(!used[i])dfs1(i);
    memset(used,false,sizeof(used));
    while(s[0]){
        int v=s[s[0]--];
        if(!used[v])dfs2(v,v);
    }
    //------------缩强连通分量-------------
    for(int i=1;i<=m;i++)
        if(fa[a[i]]!=fa[b[i]])add3(fa[a[i]],fa[b[i]]);
    //----------------拓扑排序-------------
    h=1,t=0;
    for(int i=1;i<=n;i++)
        if(fa[i]==i&&d[i]==0)q[++t]=i;
    while(h<=t){
        int x=q[h++],ptr=last3[x];
        while(ptr){
            int y=target3[ptr];
            d[y]--;
            if(d[y]==0)q[++t]=y;
            ptr=prev3[ptr];
        }
    }
    //-----------------求最长路------------------
    bool flag=false;
    for(int i=1;i<=n;i++)f[i]=-INF;
    f[fa[start]]=sum[fa[start]];
    ans=-INF;
    for(int i=1;i<=t;i++){
        if(q[i]==fa[start])flag=true;
        if(flag){
            int x=q[i],ptr=last3[x];
            if(bar[x])ans=max(ans,f[x]);
            while(ptr){
                int y=target3[ptr];
                f[y]=max(f[y],f[x]+sum[y]);
                ptr=prev3[ptr];
            }
        }
    }
    printf("%d",ans);
    return 0;
}

END

PS:本篇所有图片均由graphviz绘制。

感谢@Chanis 的指导