萌新妹子求救
查看原帖
萌新妹子求救
718017
Dream__maker楼主2024/2/25 23:11

这份代码怎么加路径压缩 qwq?虽然过了

#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 1e5 + 5 ; 
int n , fa[N] , ans = N , deep ; 
int find(int x)
{
	deep ++ ; 
	if(fa[x] == x) return x ; 
	return find(fa[x]) ; 
}
int main()
{
	cin >> n ; 
	for(int i = 1 ; i <= n ; i ++) fa[i] = i ; 
	for(int i = 1 , a ; i <= n ; i ++)
	{
		scanf("%d" , &a) ; 
		deep = 0 ; 
		if(find(a) == i) ans = min(ans , deep) ; 
		else fa[i] = a ; 
	}
	cout << ans << endl ; 
	return 0;
}
2024/2/25 23:11
加载中...