数据结构-模板-并查集(路径压缩+按秩合并)
数据结构-模板-并查集(路径压缩+按秩合并)
所谓并查集就是将编号为1~n的n个对象划分为不相交集合，在每个集合中，选择其中的某个元素代表所在集合在这个集合中，并查集的操作有初始化，合并，查找。
#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);typedef long long ll;typedef unsigned long long ull;const int MAXN=1e4;const int MOD=1e6;struct SET{
int date[MAXN+100]; int h[MAXN+100]; void init(int n){ for(int i=1;i<=n;++i){
date[i]=i;
}
}
int find(int x){//dfs+路径压缩，路径压缩可以把单次合并平均时间复杂度降至O(α(n)),即反阿克曼函数，可视为常函数。但是最坏也有O(logn)。
if(x!=date[x]) date[x]=find(date[x]); return date[x];
} void merge(int x,int y){//合并，找到x和y的根节点后合并
x=find(x);
y=find(y); if(x!=y) date[x]=date[y];
} //下面是按秩合并，可以让时间复杂度最坏也有O(α(n))，按秩合并也就是同时记录树的深度，把浅的树并在深的上。
void merge_plus(int x,int y){
x=find(x);
y=find(y); if(h[x]==h[y]){
++h[x];
date[y]=date[x];
} else{ if(h[x]<h[y]) date[x]=date[y]; else date[y]=date[x];
}
}
}sett;//以上是并查集内容int main(){ int n,m,x,y,op; cin>>n>>m;
sett.init(n); while(m--){ cin>>op>>x>>y; if(op==1) sett.merge(x,y); else{ if(sett.find(x)==sett.find(y)) cout<<'Y'; else cout<<'N'; cout<<'\n'; // print(n);
}
} return 0;
}