【BZOJ】1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果
【算法】基环树DP
【题意】给定若干有向基环树，每个点能走的最远路径长度。
【题解】
参考：【BZOJ1589】Trick or Treat on the Farm 基环树裸DP by 空灰冰魂
考虑DAG上DP，令f[x]表示点x开始能到达的最远长度，则f[x]=f[y]+1,x--->y。
环套树最重要的操作就是找环，可以用tarjan缩点，也可以用简单的找环写。
找环：在vis上给访问过的点标号，从每个未访问过的点开始遍历，用栈存储路上的点，遇到vis标号相同的点说明找到环，然后弹出。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100010; int nex[maxn],s[maxn],n,f[maxn],top,vis[maxn]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&nex[i]); for(int i=1;i<=n;i++)if(!vis[i]){ int j=i; top=0; while(!vis[j]){ vis[j]=i; s[++top]=j; j=nex[j]; } if(vis[j]==i){ int cnt=1; while(s[top-cnt+1]!=j)cnt++; for(int k=1;k<=cnt;k++)f[s[top-k+1]]=cnt; top-=cnt; } int k=0; while(top>0)f[s[top--]]=f[j]+(++k); } for(int i=1;i<=n;i++)printf("%d ",f[i]); return 0; }