P1137 旅行计划

/*拓扑排序去寻找点的拓扑序

便于DP，那么怎么去找

首先邻接表存边，然后dfs搜寻每一个点

最后进行拓扑排序，找到拓扑序*/

#include<bits/stdc++.h>

const int maxn = ;

const int maxm = ;

using namespace std;

int n,m,p=;

int a,b;

int dp[maxn];

int h[maxn],v[maxm],zrj[maxm];

void add(int a,int b)

{

    zrj[p]=h[b];

    h[b]=p;

    v[p]=a;

    p++;

}

int dfs(int y,int x)

{

    if (dp[x]) return dp[x];

    for (int j=h[x],u=v[j]; j; j=zrj[j],u=v[j])

    {

        dp[x]=max(dfs(y+,u)+,dp[x]);

    }

    return dp[x];

}

int main()

{

    cin>>n>>m;

    for (int i=; i<=m; i++)

    {

        cin>>a>>b;

        add(a,b);

    }

    for (int i=n; i>=; i--)

        dfs(,i);

    for (int i=; i<=n; i++)

        cout<<dp[i]+<<endl;

    return ;

}