第一个点AC,其他WA
查看原帖
第一个点AC,其他WA
792595
wbw_121124楼主2023/11/21 17:30

可以帮我调一下吗???


#include <bits/stdc++.h>
#define debug true
using namespace std;
int n, next[100005];
int fa[100005];
int sw[100005];
int find(int x)
{
	if (fa[x] == x)
		return x;
	return fa[x] = find(fa[x]);
}
void unionn(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y)
		fa[x] = y;
	return;
}
void get(int x, int y)
{
	if (find(x) == find(y))
	{
		int cnt = 1;
		for (int i = x; i != y; i = fa[i])
			cnt++;
		for (int i = x; i != y; i = fa[i])
			sw[i] = cnt;
		sw[y] = cnt;
		return;
	}
	unionn(y, x);
	fa[y] = x;
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	for (int i = 1; i <= n; i++)
	{
		cin >> ::next[i];
		get(::next[i], i);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!sw[i])
		{
			int cnt = 1, j;
			for (j = fa[i]; !sw[j]; j = fa[j])
				cnt++;
			sw[i] = cnt + sw[j];
		}
		cout << sw[i] << '\n';
	}
	return 0;
}
2023/11/21 17:30
加载中...