虽然已经A了但还是想知道之前的做法为什么不对qwq

回复帖子

@cellur925 2018-08-16 08:57 回复

RT.

感觉差异不是很大啊... 求dalao指点。蟹蟹qwq

是记录前驱最后统一处理的办法

#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

int n,m,x,y,tot,cnt;
int head[100090],du[100090],pre[100090],f[100090],a[100090];
struct node{
    int next,to;
}edge[200090];

void add(int x,int y)
{
    edge[++tot].to=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

void topo()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(!du[i]) q.push(i),f[i]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        a[++cnt]=u;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(--du[v]==0) q.push(v),pre[v]=u;
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&x,&y),add(x,y),du[y]++;
    topo();
    for(int i=1;i<=n;i++)
        f[i]=f[pre[i]]+1;
    for(int i=1;i<=n;i++)
        printf("%d\n",f[i]);
    return 0;
}
@LDlornd 2018-08-16 09:14 回复

因为初始条件是: $\ dp[i]=1\ (du[i]==1)\ $,而不是$\ dp[1]=1\ $啊,你不是已经找出错误来了么,事实上$\ 1\ $这个点不一定在最西边啊。。。