集合的存储
1、数组
2、STL的vector
3、链表（时间不够优秀）或者STL的list
4、森林存储，也就是fa[]
优化技术
1、启发式合并
每次将较小的集合合并到较大的集合中去，大小可以是size[]，也可以是深度de[]，或者是其他的
2、路径压缩
int fa[maxn],size[maxn];
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]); //路径压缩
}
void onion(int x,int y){
int fax=find(x);
int fay=find(y);
if(size[fax]>size[fay]) swap(x,y); //启发式合并
fa[fax]=fay;
size[fay]+=size[fax];
}
应用
1、亲戚
https://www.luogu.com.cn/problem/P1551
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=5010;
const int INF=0x3fffffff;
int fa[maxn];
int n,m,p,x,y;
int find(int x){
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
void onion(int x,int y){
int fa1=find(x);
int fa2=find(y);
if(fa1!=fa2) fa[fa1]=fa2;
}
int main(){
scanf("%d %d %d",&n,&m,&p);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
onion(x,y);
}
for(int i=1;i<=p;i++){
scanf("%d %d",&x,&y);
if(find(x)!=find(y)) printf("No\n");
else printf("Yes\n");
}
return 0;
}
2、银河英雄传说
https://www.luogu.com.cn/problem/P4847
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=30010;
const int INF=0x3fffffff;
//在线查询的题目
//有的需要路径压缩，有的不需要
int fa[maxn],size[maxn],dis[maxn];
//dis[]就是每个点距离它的fa的距离，不能进行压缩
int find(int x){
if(x==fa[x]) return x;
int ff=find(fa[x]);
dis[x]+=dis[fa[x]]; //没有压缩
return fa[x]=ff; //压缩 ！！！！！这里是关键
}
void onion(int x,int y){
int fa1=find(x);
int fa2=find(y);
if(fa1==fa2) return;
fa[fa1]=fa2;
dis[fa1]+=size[fa2]; //把fa1连在fa2后面
size[fa2]+=size[fa1]; //整个队伍的长度 ！！！！这里是关键
}
int t;
int main(){
scanf("%d",&t);
char a[10]; //不要用char a,因为还要控制输入很麻烦
int x,y;
for(int i=1;i<=30000;i++) {
fa[i]=i;
size[i]=1;
} //不要忘了初始化
//getchar();
while(t--){
scanf("%s",a);
if(a[0]==‘M‘){
scanf("%d %d",&x,&y);
onion(x,y);
}
else {
scanf("%d %d",&x,&y);
int fa1=find(x),fa2=find(y);
if(fa1!=fa2){
printf("-1\n");
}
else{
printf("%d\n",abs(dis[x]-dis[y])-1);
}
}
//getchar();
}
return 0;
}
3、关押罪犯
https://www.luogu.com.cn/problem/P1525
合并敌人的敌人与自己，并且注意敌人的表示方法，x的敌人是x+n
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=20010;
const int mm=100001;
const int INF=0x3fffffff;
//用贪心的思想，把仇恨值从大到小排序
//然后让排在前面的仇恨值最大的x,y放在两个集合里面，同时维护x的敌人x‘,y的敌人y‘,在分开x，y的时候，要合并x和y‘，x‘和y
//在合并的时候如果 x和y‘或者x‘和y已经在一个集合里面了，那么此时的仇恨值就是最小的
struct node{
int x,y,w;
bool operator <(const node& x)const{
return w>x.w ; //注意重载小于符号的写法
}
}a[mm]; //存储的是关系
int n,m;
int fa[2*maxn]; //为什么要*2？？？因为！！！！x的敌人表示为x+n，注意这种表示方法
int find(int x){
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=2*n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].w);
}
sort(a+1,a+1+m);
for(int i=1;i<=m;i++){
int x=a[i].x,y=a[i].y,w=a[i].w;
int fa1=find(x),fa2=find(y);
if(fa1==fa2){ //如果在一个集合里面
printf("%d\n",w); //就输出当前的仇恨值
return 0;
}
else{
fa[fa1]=find(y+n); //注意写法啊啊啊
fa[fa2]=find(x+n);
}
}
printf("0\n");
return 0;
}
4、食物链
https://www.luogu.com.cn/problem/P2024
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=50004;
const int INF=0x3fffffff;
int fa[maxn*3]; //x表示x，x+n表示x吃的，x+2*n表示吃x的
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void oni(int x,int y){
int aa=find(x);
int aa1=find(y);
if(aa!=aa1) fa[aa]=fa[aa1];
}
bool same(int x,int y){
return find(x)==find(y); //表示x与y是不是在一个集合
}
int n,k,flag,x,y;
int main(){
int ans=0;
scanf("%d %d",&n,&k);
for(int i=1;i<=3*n;i++) fa[i]=i;
while(k--){
scanf("%d %d %d",&flag,&x,&y);
if(x>n||y>n){
ans++;
continue;
}
if(flag==1){ //x与y是不是捕食关系
if(same(x+n,y)||same(x+2*n,y)){
ans++;
}
else{
oni(x,y);
oni(x+n,y+n);
oni(x+2*n,y+2*n);
}
}
else if(flag==2){ //x吃y
if(x==y){
ans++;
continue;
}
if(same(x,y)||same(x+2*n,y)){
ans++;
}
else{
oni(x,y+2*n); //
oni(x+n,y);
oni(x+2*n,y+n);
}
}
}
printf("%d\n",ans);
return 0;
}
原文：https://www.cnblogs.com/shirlybaby/p/12287532.html