并查集的基本操作:

1.合并两个集合

2.查询两个元素的祖宗节点

扩展:

1.记录每个集合的大小 将集合大小绑定到代表元素节点上 就是并查集的思想 (不是每个元素都是正确的 但是代表元素是正确的)

2.记录每个点到根节点的距离 绑定到每个元素身上 因为每个元素到根节点的距离都是不一样的

边带权的并查集

边带权并查集，顾名思义，就是各个结点之间带有权值的并查集，在查询和合并时可以维护结点之间的权值。边带权并查集可以用于统计每个节点到树根之间路径上的一些信息。

扩展域并查集

扩展域用以维护较抽象的对象之间的逻辑关系，由于有点抽象，所以理解起来有点费劲。

扩展域将数据之间的关系分类，将对象之间不同的关系种类分开讨论，并在这些数据之间建立联系。

假定现在要维护要k类集合 如果k不大两个都行  k大就选边带权

---

 

1.格子游戏

信息学奥赛一本通（C++版）在线评测系统

题意问第一次连成圈是什么时候

分析一下形成环的条件就是在连边的时候 边的两个端点已经在一个集合里面了 直接并查集

细节：把两位坐标转换为一维 (x,y)-->x*n+y x y从0开始

#include <bits/stdc++.h>
using namespace std;
const int N=40010;
int n,m;
int p[N];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
int get(int x,int y)
{return x*n+y;
}
int main()
{cin>>n>>m;for(int i=0;i<n*n;i++)p[i]=i;int res=0;for(int i=1;i<=m;i++){int x,y;char d;cin>>x>>y>>d;x--,y--;int a=get(x,y);int b;if(d=='D'){b=get(x+1,y);}else b=get(x,y+1);int pa=find(a),pb=find(b);if(pa==pb){res=i;break;}p[pa]=pb;}if(!res) puts("draw");else cout<<res<<endl;return 0;
}

2.搭配购买

信息学奥赛一本通（C++版）在线评测系统

分析过后就可以知道我们每次只能去买一组云 然后会得到一个体积和价值 那么这不就是01背包吗

让后用并查集维护好每一组就ok了

看起来像有依赖的背包问题 但是不是 因为这里要买一个物品就要把全部物品都买了 而有依赖的背包问题是要买后者就要买前者这种条件

#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,vol;
int v[N],w[N];
int p[N];
int f[N];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
int main()
{cin>>n>>m>>vol;for(int i=1;i<=n;i++)p[i]=i;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];while(m--){int a,b;cin>>a>>b;int pa=find(a),pb=find(b);if(pa!=pb){v[pb]+=v[pa];w[pb]+=w[pa];p[pa]=pb;}}for(int i=1;i<=n;i++)if(p[i]==i){for(int j=vol;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);}cout<<f[vol]<<endl;return 0;
}

3.程序自动分析

237. 程序自动分析 - AcWing题库

由于数据范围很大 但是操作数很小 所以要离散化

1.约束条件的顺序是无所谓的 所以可以先考虑所有的相等元素 这里是不会有矛盾的

2.再去考虑所有不等的元素 如果不等的元素已经在一个集合了 那肯定是矛盾的

并查集维护就行了

#include <bits/stdc++.h>
using namespace std;
const int N=2000010;
int n,m;
int p[N];
unordered_map<int,int> mp;
struct node
{int x,y;int e;
}query[N];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
int get(int x)
{if(mp.count(x)==0) mp[x]=++n;return mp[x];
}
int main()
{int t;cin>>t;while(t--){n=0;mp.clear();cin>>m;for(int i=0;i<m;i++){int x,y,e;cin>>x>>y>>e;query[i]={get(x),get(y),e};}for(int i=1;i<=n;i++) p[i]=i;for(int i=0;i<m;i++){if(query[i].e==1){int pa=find(query[i].x),pb=find(query[i].y);p[pa]=pb;}}bool has_conflict=false;for(int i=0;i<m;i++)if(query[i].e==0){int pa=find(query[i].x),pb=find(query[i].y);if(pa==pb){has_conflict=true;break;}}if(has_conflict) puts("NO");else puts("YES");}return 0;
}

4.奇偶游戏

239. 奇偶游戏 - AcWing题库

用前缀和的思想去思考 s[ l ~ r ]中有奇数个1代表 s[ r ] - s[ l - 1 ] 中有奇数个1 代表s[r]和s[l-1]奇偶性不同    偶数个1的话就是s[r]和s[l-1]奇偶性相同

但是奇偶性无矛盾一定可以推出来该问题无矛盾？

令a[i]=| s[i]-s[i-1] | 一定可以构造出来一个无矛盾的方案 所以是等价的

带边权并查集

 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int p[N],d[N];//s表示集合的长度，d表示每个点到根节点的距离
int n,m;
unordered_map<int,int> ha;
int get(int x)
{if(!ha.count(x)) ha[x]=++n;return ha[x];
}
int find(int x)
{if(p[x]!=x) {int root=find(p[x]);d[x]^=d[p[x]];//更新路径长其他的值p[x]=root;}return p[x];
}
int main()
{cin>>n>>m;n=0;int res=m;for(int i=0;i<N;i++) p[i]=i;//初始化for(int i=1;i<=m;i++){int a,b;string type;cin>>a>>b>>type;a=get(a-1),b=get(b);//获取离散化后的值int t=0;if(type=="odd") t=1;//假如是奇数int pa=find(a),pb=find(b);if(pa==pb)//假如在一个集合{if((d[a]^d[b])!=t)//假如跟t不同类{res=i-1;break;}}else//反之不在一个集合就合并{p[pa]=pb;d[pa]=d[a]^d[b]^t;//合并到同一类中}}cout<<res<<endl;return 0;
}

扩展域并查集

 

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=N/2;//M是分界线在0-M是偶数，大于M是奇数
int p[N],d[N];//s表示集合的长度，d表示每个点到根节点的距离
int n,m;
unordered_map<int,int> ha;
int get(int x)
{if(!ha.count(x)) ha[x]=++n;return ha[x];
}
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
int main()
{cin>>n>>m;n=0;int res=m;for(int i=0;i<N;i++) p[i]=i;//初始化for(int i=1;i<=m;i++){int a,b;string type;cin>>a>>b>>type;a=get(a-1),b=get(b);//获取离散化后的值int a1=find(a),a2=find(a+M),b1=find(b),b2=find(b+M);//获取a跟b的偶数和奇数情况if(type=="odd")//假如是奇数类型{if(a1==b1||a2==b2)//但是a跟b同类了{res=i-1;break;}p[a1]=b2;//反之把a的偶数合并到b的奇数p[a2]=b1;//反之把a的奇数合并到b的偶数}else//假如是偶数{if(a1==b2||a2==b1)//假如不同类{res=i-1;break;}p[a1]=b1;//把偶数合并到偶数里p[a2]=b2;//把奇数合并到奇数里}}cout<<res<<endl;return 0;
}

5.银河英雄传说

238. 银河英雄传说 - AcWing题库

题目的两个操作：1.合并集合 2.两点间距离 用并查集维护到根节点的距离就行了

1.让排头当根节点

2.d[pa]=size[pb]

3.size[pb]+=size[pa]

 

 

看到这里会不会有疑惑 就是说明明我是find完pa pb以后再将d[pa]=size[pb] size[pb]+=size[pa]的那为什么可以能维护每个点道根节点的距离的 也就是这段代码

        if(op[0]=='M'){int pa=find(a),pb=find(b);if(pa!=pb){d[pa]=s[pb];s[pb]+=s[pa];p[pa]=pb;}}

 其实呢更新每个点到根节点的距离是在查询的时候更新的

        else{int pa=find(a),pb=find(b);//这里更新的捏if(pa!=pb) puts("-1");else printf("%d\n",max(0,abs(d[a]-d[b])-1));}

完整代码 

#include <bits/stdc++.h>
using namespace std;
const int N=30010;
int n,m;
int p[N],s[N],d[N];
int find(int x)
{if(p[x]!=x){int root=find(p[x]);d[x]+=d[p[x]];p[x]=root;}return p[x];
}
int main()
{cin>>m;for(int i=1;i<=N;i++){p[i]=i;s[i]=1;}while(m--){char op[2];int a,b;cin>>op>>a>>b;if(op[0]=='M'){int pa=find(a),pb=find(b);if(pa!=pb){d[pa]=s[pb];s[pb]+=s[pa];p[pa]=pb;}}else{int pa=find(a),pb=find(b);if(pa!=pb) puts("-1");else printf("%d\n",max(0,abs(d[a]-d[b])-1));}}return 0;
}