模板并查集

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl "\n"
const int maxn=3e5+5;
#define PII pair<int,int>
const double EPS = 1e-12;
int ans[maxn],d[maxn];
int f[maxn];
int getRoot(int x) {
	//i节点当前的父节点是谁 
    return x == f[x] ? x : f[x] = getRoot(f[x]);
}
void merge(int x,int y){
	//两个集合合并 
    int fx=getRoot(x),fy=getRoot(y);
    if(fx!=fy){
        f[fx]=fy;
    }
    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    while(q--){
        int x,y,op;
        cin>>op>>x>>y;
        if(op==1){
            merge(x,y);
        }
        else
        {
            int fx=getRoot(x),fy=getRoot(y);
            if(fx==fy){
                cout<<"Y"<<endl;
            }
            else{
                cout<<"N"<<endl;
            }
        }

    }
    

}

亲戚

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl "\n"
const int maxn=3e5+5;
#define PII pair<int,int>
int f[maxn];
//f[i]的含义是 i节点的父节点是谁 
int getRoot(int x){
	//找到x的根节点
	if(x==f[x]){
		return x;
	} 
	else{
		//x的根节点是 f[x]的根节点 
		return f[x]=getRoot(f[x]);
	}
	
}
/*
5 5
1 1 2
1 1 3
1 4 5
1 1 5
2 2 4
*/
void merge(int x,int y){
//	f[x]=y;
	int fx=getRoot(x),fy=getRoot(y);
	f[fx]=fy;
}

signed main(){
	int n,p,q;
	cin>>n>>p>>q;
	
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=p;i++){
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		int fx=getRoot(x),fy=getRoot(y);
		if(fx==fy){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	}
	
}

pSort

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl "\n"
const int maxn=3e5+5;
#define PII pair<int,int>
const double EPS = 1e-12;
int ans[maxn],d[maxn];
int f[maxn];
int getRoot(int x) {
    return x == f[x] ? x : f[x] = getRoot(f[x]);
}
void merge(int x,int y){
    int fx=getRoot(x),fy=getRoot(y);
    if(fx!=fy){
        f[fx]=fy;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ans[i];
        f[i]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(j-i==d[i]||j-i==d[j]){
                merge(i,j);
            }
        }
    }
    int f=1;
    for(int i=1;i<=n;i++){
        int fx=getRoot(i),fy=getRoot(ans[i]);
        if(fx!=fy){
            f=0;break;
        }
    }
    if(f){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
    

}