https://www.luogu.com.cn/problem/P2921

题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在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

1
2
3
4
5
4 
1 
3 
2 
3

输出 #1

1
2
3
4
1 
2 
2 
3

样例解释

有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个隔间。

翻译提供者：吃葡萄吐糖

先用 tarjan 找出所有的强连通分量 ( 包括强连通分量的大小 )，然后再跑一边 dfs

搜索的时候，如果 u, v 不在一个圈内，则 ans [ u ] = 1 + ans[ v ]，需 dfs( v ) 先求出 ans[ v ] ; 否则两者相等，直接返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
const int MAX=100000+10; 
int n,next[MAX],ans[MAX];
int Low[MAX],DFN[MAX],Stack[MAX],Belong[MAX];
int ind,top;
int scc;   //强连通分量的个数 
bool InStack[MAX];
int num[MAX];//各个强连通分量包含点的个数
void tarjan(int u,int fa){
	Low[u]=DFN[u]=++ind;
	Stack[top++]=u;
	InStack[u]=true;
	int v=next[u];
	if(!DFN[v]){
		tarjan(v,u);
		Low[u]=min(Low[u],Low[v]);
	}else if(InStack[v]){
		Low[u]=min(Low[u],DFN[v]);
	}
	if(Low[u]==DFN[u]){
		scc++;
		do{
			v=Stack[--top];
			InStack[v]=false;
			Belong[v]=scc; //标记属于哪一个强连通分量
			num[scc]++;
		}while(v!=u);
	}
} 
void dfs(int u){
	if(ans[u]) return;
	int v=next[u];
	if(Belong[v]!=Belong[u]){
		dfs(v);
		ans[u] = 1 + ans[v];
	}else {
		ans[u] = num[Belong[u]];
		dfs(v) ;
	}
}
void solve(int n){
	memset(DFN,0,sizeof(DFN));
	memset(InStack,false,sizeof(InStack));
	memset(num,0,sizeof(num));
	ind=scc=top=0;
	for(int i=1;i<=n;i++)
		if(!DFN[i])
			tarjan(i,-1);
}
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,1,n+1){
		sf(next[i]);
	}
	solve(n);
	fi(i,1,n+1)
		if(!ans[i])
			dfs(i);
	fi(i,1,n+1){
		pf(ans[i]);
		pfc("\n");
	}
	return 0;
}