并查集

话说这个不应该是签到题吗? 怎么上强度了qwq

#include <iostream>
#include <string>
#include <vector>
#include <numeric>

using namespace std;

using ll = long long;

struct USet {
	vector<int> fa;
	vector<int> cnt;
	int cc;
	
	USet(int size)
		: fa(vector<int>(size))
		, cnt(vector<int>(size, 1))
		, cc(size)
	{
		iota(fa.begin(), fa.end(), 0);
	}
	
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	
	void maga(int from, int to) {
		int x = find(from);
		int y = find(to);
		if (x == y)
			return;
		fa[x] = y;
		cnt[y] += cnt[x];
	}
	
	bool isSame(int x, int y) {
		return find(x) == find(y);
	}
	
	int getCnt(int x) {
		return cnt[find(x)];
	}
};

int main() {
	int n;
	cin >> n;
	USet uset(n);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		uset.maga(x - 1, i);
	}
	int res = 0;
	for (int i = 0; i < n; ++i) {
		res = max(res, uset.getCnt(i));
		if (i > 0) {
			if (!uset.isSame(i - 1, i))
				res = max(res, uset.getCnt(i - 1) + uset.getCnt(i));
		} else if (i < n - 1) {
			if (!uset.isSame(i + 1, i))
				res = max(res, uset.getCnt(i + 1) + uset.getCnt(i));
		}
	}
	cout << res << '\n';
	return 0;
}