旅行计划

题目传送门

解题思路

这题就是拓扑排序+dp
先拓扑排序找相连的点
再用dp统计答案

拓扑排序

AC代码

#include<iostream>
using namespace std;
int n,m,x,y,h,t,num,tot,b[100005],c[100005],p[100005],head[200005],f[100005];
struct stu
{
   
	int to,next;
}a[200005];
void add(int x,int y)//邻接表
{
   
	tot++;
	a[tot].to=y;
	a[tot].next=head[x];
	head[x]=tot;
}
void tp()//拓扑排序
{
   
    for(int i=1;i<=n;i++)
	if(b[i]==0)
	{
   
		p[++t]=i;
		c[i]=1;
	}
    while(h<t)
    {
   
    	h++;
        int k=p[h];
        for(int i=head[k];i;i=a[i].next)
         if(c[a[i].to]==0)//标记
		  {
   
            b[a[i].to]--;//度
            if(b[a[i].to]==0)//度为0就退出
			{
   
				c[a[i].to]=1;
				p[++t]=a[i].to;
			}
          } 
    }
}
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
   
		cin>>x>>y;
		add(x,y);//建图
		b[y]++;//标记
	}
	tp();
	for(int i=1;i<=n;i++)f[i]=1;//dp
    for(int i=1;i<=n;i++)
     for(int j=head[p[i]];j;j=a[j].next)
      f[a[j].to]=max(f[a[j].to],f[p[i]]+1);
	for(int i=1;i<=n;i++)
	 cout<<f[i]<<endl;
}

谢谢