并查集加上stl

解题思路:

典型的并查集问题。同一个集合上可以相互跳跃。
利用并查集，把所有元素合并，然后利用集合map统计各个根节点拥有的元素个数，然后利用优先队列，弹出前两个元素即为两个最大集合的数量，注意只有一个集合的情况。
注意事项:

参考代码:

#include<bits/stdc++.h>
#define  endl '\n' 
using namespace std;
using ll = long long;
const int N = 1e6+10;
int a[N];
int fa[N];
int cnt[N];
int find(int x){
	if(x == fa[x])	return x;
	return fa[x] = find(fa[x]);//路径压缩
}
void uni(int x,int y){
	int xx = find(x),yy = find(y);
	fa[x] = find(y);	
}
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		fa[i] = i;
	}
	//合并
	for(int i = 1; i<= n; i++){
		uni(i,a[i]);
	}
	//把根节点统计个数
	//注意一定要用find来寻找最后的根节点
	map<int,int> m;
	for(int i = 1; i <= n; i++){
		m[find(i)]++;
	}
	//利用优先队列的前两个元素一定是最大的两个并查集
	int x1=0,x2=0;
	priority_queue<int> q;
	for(auto i : m){
		q.push(i.second);
	}
	//需要注意只有一种集合的情况
	x1 = q.top(),q.pop();
	if(!q.empty())	x2 = q.top();
	cout << x1 + x2 ;
} 
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t = 1;
	while(t--)	solve();
	return 0;
}