并查集加一次扫描

解题思路:
并查集求最大联通快、

然后扫描的时候 相邻不在同一个并查集就直接把两个集合加起来取最大
注意事项:

参考代码:

#include <iostream>

#include<vector> 

#include<algorithm>

#define ll long long

#define endl "\n"

using namespace std;

int n, m, k; int T, ncase = 0; const int N = 1e6 + 3, mod = 1e9 + 7;

int a[N]; int fa[N], siz[N]; 

int find(int x) {

if (fa[x] != x)return fa[x] = find(fa[x]);

return fa[x];

}

int main()

{

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i]; fa[i] = i; siz[i] = 1;

}

ll ans = 0;

for (int i = 1; i <= n; i++) {

int cnt = i;

do {

int rx = find(cnt);

int ry = find(a[cnt]);

if (rx == ry)break;

fa[rx] = ry; 

siz[ry] += siz[rx];

m = max(m, siz[ry]);

cnt = a[cnt];

} while (cnt!=a[cnt]);

}

for (int i = 2; i <= n; i++) {

if (fa[i] != fa[i - 1]) {

m = max(siz[fa[i]]+ siz[fa[i - 1]],m);

}

}cout << m;

return 0;

}