洛谷

洛谷

题目描述
每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。
由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。
FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。
在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。
输入格式
第1行 整数n。
第2行到n+1行 每行包含一个整数 next_i 。
输出格式
n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。

输入输出样例
输入样例#1：
4
1
3
2
3

输出样例#1：
1
2
2
3

解释：首先缩点，然后统计每个点的个数，最后我们用f[i]表示从i出发可以到达的点的个数，即直接记忆化搜索一下就好了

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 1e5 + 1e4, maxm = 1e5 + 1e4;
int Index,pd[maxn],DFN[maxn],LOW[maxn];
int tot,color[maxn],sum[maxn],f[maxn];
int edge,fir[maxn],Next[maxm],to[maxm];
int sta[maxn],top; //手写栈
int n,m,val[maxn],y[maxm],ans;
void add(int x,int y){to[++edge]=y; Next[edge]=fir[x]; fir[x]=edge;
}
void tarjan(int x){sta[++top]=x;pd[x]=1;DFN[x]=LOW[x]= ++Index;for(int i=fir[x];i;i=Next[i]){int v=to[i];if(!DFN[v]){tarjan(v);LOW[x]=min(LOW[x],LOW[v]);}else if(pd[v]){LOW[x]=min(LOW[x],DFN[v]);}}if(DFN[x]==LOW[x]){tot++;while(sta[top+1]!=x){color[sta[top]]=tot;pd[sta[top--]]=0;}}
}
void search(int x){if(f[x]) return;f[x]+=sum[x];for(int i=fir[x];i;i=Next[i]){int v=to[i];search(v);f[x]+=f[v];}
}
int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>y[i];add(i,y[i]);}for(int i=1;i<=n;i++) if(!DFN[i]) tarjan(i);memset(fir,0,sizeof(fir));memset(Next,0,sizeof(Next));memset(to,0,sizeof(to));edge=0;for(int i=1;i<=n;i++){sum[color[i]]++;if(color[i]!=color[y[i]])add(color[i],color[y[i]]);}for(int i=1;i<=tot;i++){search(i);}for(int i=1;i<=n;i++){cout<<f[color[i]]<<endl;}return 0;
}