题解P1137【旅行计划】(拓扑排序)

2018-04-29 16:50:07


以前都一直不懂拓扑排序是个什么东西,看了一下发现还是蛮简单的

拓扑排序是给一个有向无环图(DAG)上的点进行排序,排成线性序列,使排序后的点满足所有的边u->v,在这个序列中,u都在v的前面。

如果还是没明白的话,来举个栗子,如下图

序列v6–>v1—->v4—>v3—>v5—>v2就是一个满足拓扑排序要求的序列,当然v1–>v6—->v4—>v3—>v5—>v2,也是可以的

具体怎么做呢?首先找到入度为0的点。因为入度为0的点肯定排在最前面,任意去掉一个入度为0的点和它的边,再次统计入度为0的点并重复这个过程,像这样:

我们先去掉了v6,这时入度为0的点只剩下v1,所以再去掉v1

这时v3,v4都可以去掉,我们去掉v4

然后再是v3

再是v5,v2,就得到了v6–>v1—->v4—>v3—>v5—>v2这个序列

最后得到的序列会因程序而异。



题解部分

很明显这题可以用拓扑排序,只需要记录一下每个点是第几轮被去掉的就可以了。因为第几轮被去掉就代表了它之前有几个点过来。这里的一轮是指所有入度为0的点同一时间去掉算一轮。具体看代码吧。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,cnt=0;
int head[200100],nxt[200100],to[200100];
int in[100100],ans[100100];
int q[100100],f[100100];
void addedge(int x,int y)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
void tpsort()
{
    int l=0,r=0;
    for(int i=1;i<=n;i++)
        if(in[i]==0) q[++r]=i,f[i]=1;//先将入度为0的点进队列,并且记录下这些点将在第一轮被去掉。
    while(l<=r)
    {
        int u=q[++l];
        for(int i=head[u];i!=-1;i=nxt[i])
        {
            int v=to[i];
            if(f[v]) continue;
            in[v]--;//去掉与这个点有关的边,相连的点的入度减1
            if(in[v]==0)
            {//如果相连的点入度为0了,进队列,进行删点
                f[v]=f[u]+1;//可以说是一个小小的DP,这个点必然是在当前点的后一轮删除的
                q[++r]=v;
            }
        }
    }
}
int main()
{
    memset(in,0,sizeof(in));
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);//加边
        in[y]++;//记录入度
    }
    tpsort();
    for(int i=1;i<=n;i++)
        cout<<f[i]<<endl;
    return 0;
}