先进行拓扑排序得到拓扑序

之后按拓扑序dp求最大值

#include
    
     #include
     
      using namespace std;const int MAX=100005;int n,m,cnt;int head[MAX],top[MAX],sta[MAX],ans[MAX],du[MAX];struct edg{    int to,next;}edge[MAX*2];void add(int x,int y){    edge[++cnt].next=head[x];    edge[cnt].to=y;    head[x]=cnt;}void tpsort(){
   //拓扑排序 top即拓扑序    int tot=0,hea=1,tai=0;    for(int i=1;i<=n;i++)        if(!du[i]) sta[++tai]=top[++tot]=i;    while(hea<=tai){        int u=sta[hea];        for(int i=head[u];i;i=edge[i].next){            int v=edge[i].to;            du[v]--;            if(!du[v]) sta[++tai]=top[++tot]=v;        }        hea++;    }}int main(){    scanf("%d %d",&n,&m);    for(int i=1;i<=m;i++){        int a,b;        scanf("%d %d",&a,&b);        add(a,b);        du[b]++;    }    tpsort();    for(int i=1;i<=n;i++){        int u=top[i];        for(int j=head[u];j;j=edge[j].next){            int v=edge[j].to;            ans[v]=max(ans[u]+1,ans[v]);//简单dp        }    }    for(int i=1;i<=n;i++) printf("%d\n",ans[i]+1);    return 0;}