P1137 旅行计划

原题链接

题解

拓扑排序+dp。

首先以入度为零的结点为起始结点，其游览城市数量为1，接下来每到下一结点，游览城市数++；即当前结点的游览城市数是上一结点的游览数+1，并取最大值。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int head[N],Next[N*2],to[N*2],sum[N],pre[N],cnt=1,que[N];
void build(int x,int y){
    Next[cnt]=head[x];
    to[cnt]=y;
    head[x]=cnt;
    sum[y]++;
}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        build(x,y);
        cnt++;
    }
    int l=0,r=0;
    for (int i=1;i<=n;i++){
        if (sum[i]==0){
            que[r++]=i;
            pre[i]=1;
        }
    }
    while (l<r){
        int fi=que[l];
        for (int i=head[fi];i>0;i=Next[i]){
            if (--sum[to[i]]==0){
                que[r++]=to[i];
                pre[to[i]]=pre[fi]+1;
            }
        }
        l++;
    }
    for (int i=1;i<=n;i++) printf("%d\n",pre[i]);
    return 0;
}