赛时不停的找环以及用并查集把自己卡sb了。赛后一发入魂。

题意：

给一个序列，问你从某个位置开始传书后，要传几次才能回到自己手上

q次询问，总共有n(n <= 2e5)个序列

 

题解：

模拟下样例会发现是个环，所以从某个位置开始传导后，它所到达的所有位置，从这所有位置开始后，再回到自己手上都需要相同的次数，因此可以在O(n)的情况下处理出所有存在于一个集合的数，输出即可。

 

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int p[N], anc[N], ans[N];
bool st[N];
int n, q;

//fir设定为集合的公共祖先，类似并查集
//anc存储它们的祖先
//ans主要存储集合的数个数
void find(int fir){
	int t = p[fir];
	while(t != fir){
		ans[fir]++;
		st[t] = true;
		anc[t] = fir;
		t = p[t];
	}
}

int main()
{
	scanf("%d", &q);
	while(q--){
		scanf("%d", &n);
		
		memset(st, false, (n + 5) * sizeof(bool));
		for(int i = 1; i <= n; i++)
			scanf("%d", &p[i]);
			
		for(int i = 1; i <= n; i++){
                        //只有未被纳入某个集合才能
			if(!st[i]){
				ans[i] = 1;
				st[i] = true;
				anc[i] = i;
				find(i);
			}
		}
		
		for(int i = 1; i <= n; i++)
			printf("%d%s", ans[anc[i]], (i == n) ? "\n" : " ");
	}
	
	return 0;
}