题目链接：https://www.luogu.com.cn/problem/P1137
在有向无环图上，用拓扑排序在O(n)的时间内求出最短/长路，是一个不错的选择（也称拓扑的DP）。
只需要在拓扑排序中让连的点的入度--时更新dis即可。这道题里注意一开始每一个城市都可以以自己为终点到达自己一个，所以dis的初始化应为1。
AC代码：
1 #include<cstdio> 2 #include<queue> 3 #include<iostream> 4 #include<cstring> 5 using namespace std; 6 const int N=200005; 7 queue<int> q; 8 int n,m; 9 int tot,head[N],in[N],dis[N]; 10 struct node{ 11 int to,next; 12 }edge[N]; 13 void add(int u,int v){ 14 edge[tot].to=v; 15 edge[tot].next=head[u]; 16 head[u]=tot++; 17 } 18 void toposort(){ 19 for(int i=1;i<=n;i++) if(!in[i]) q.push(i); 20 while(!q.empty()){ 21 int u=q.front(); q.pop(); 22 for(int i=head[u];i!=-1;i=edge[i].next){ 23 int v=edge[i].to; 24 in[v]--; 25 if(!in[v]) q.push(v); 26 dis[v]=max(dis[u]+1,dis[v]); 27 } 28 } 29 } 30 int main(){ 31 memset(head,-1,sizeof(head)); 32 scanf("%d%d",&n,&m); 33 for(int i=1;i<=m;i++){ 34 int x,y; 35 scanf("%d%d",&x,&y); 36 add(x,y); 37 in[y]++; 38 } 39 for(int i=1;i<=n;i++) dis[i]=1; 40 toposort(); 41 for(int i=1;i<=n;i++) printf("%d ",dis[i]); 42 return 0; 43 }