[cf] Codeforces Round #595 (Div. 3) B12 Books Exchange

前言

t a g : tag : tag:*1300 交换 思维 环 经典好题 传送门 :

题意 : 多组数据,每个人手上都有一本书,对于每个 a [ i ] a[i] a[i]表示将该书传给 a [ i ] a[i] a[i]个人。输出每个人需要多少次才可以拿到自己的书

思路 : 首先这种交换问题有很多变式,同时也非常经典,因为最终都是回到本身

因此不难发现 , 如果把交换过程进行连线, 那么能交换的 必然成一个环

然而环中每个数再次轮到本身就是环的大小

因为每个环都只是遍历一次,环中的节点也只遍历一次,所以时间复杂度 O ( T ∗ n ) O(T*n) O(T∗n)

这里给出两种写法

code :

int n;
int nx[N];
int st[N];
int ans[N];

void solve(){
	cin>>n;
	
	for(int i = 0 ;i nx[i];
		nx[i] --;
	}
	
	
	for(auto x :  nx){
		vector v;
		while(!st[x]){
			v.pb(x);
			st[x] = 1;
			x =  nx[x];
		}
		
		for(auto y : v){
			ans[y] = v.size();
		}
	}
	
	for(int i = 0 ;i