题意翻译
题目描述
每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在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只奶牛要前往的隔间数。
样例解释
有4个隔间
隔间1要求牛到隔间1
隔间2要求牛到隔间3
隔间3要求牛到隔间2
隔间4要求牛到隔间3
牛1，从1号隔间出发，总共访问1个隔间；
牛2，从2号隔间出发，然后到三号隔间，然后到2号隔间，终止，总共访问2个隔间；
牛3，从3号隔间出发，然后到2号隔间，然后到3号隔间，终止，总共访问2个隔间；
牛4，从4号隔间出发，然后到3号隔间，然后到2号隔间，然后到3号隔间，终止，总共访问3个隔间。
输入输出格式
输入格式：
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: next_i
输出格式：
* Lines 1..N: Line i contains a single integer that is the total number of unique stalls visited by cow i before she returns to a stall she has previously visited.
输入输出样例
说明
Four stalls.
* Stall 1 directs the cow back to stall 1.
* Stall 2 directs the cow to stall 3
* Stall 3 directs the cow to stall 2
* Stall 4 directs the cow to stall 3
Cow 1: Start at 1, next is 1. Total stalls visited: 1.
Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.
/* 用tarjan找环,然后缩点记录环的大小,若点在一个环中ans即为环的大小 若不在环中，即为到环的最短距离+环的大小 记忆化搜索即可 */ #include <bits/stdc++.h> using namespace std; const int maxn = 100005; int dfn[maxn],low[maxn],nex[maxn],scc_cnt,scc_amount; int stac[maxn],vis[maxn],top,scc[maxn],n,num[maxn],ans[maxn]; void tarjan(int u){ dfn[u] = low[u] = ++scc_cnt; vis[u] = 1;stac[++top] = u; int v = nex[u]; if(!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); }else if(vis[v]){ low[u] = min(low[u],dfn[v]); } if(dfn[u] == low[u]){ scc_amount++; while(stac[top] != u){ int x=stac[top--]; vis[x]=0; scc[x]=scc_amount; num[scc_amount]++; } int x=stac[top--]; vis[x]=0; scc[x]=scc_amount; num[scc_amount]++; } } int dfs(int x){ if(ans[x] > 1 || nex[x] == x) return ans[x]; return ans[x] + dfs(nex[x]); } int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++) scanf("%d",&nex[i]); for(int i = 1;i <= n;i++){ if(!dfn[i]) tarjan(i); } for(int i = 1;i <= n;i++) ans[i] = num[scc[i]]; for(int i = 1;i <= n;i++){ if(ans[i] == 1 && nex[i] != i) ans[i] = dfs(i); } for(int i = 1;i <= n;i++) printf("%d ",ans[i]); return 0; }