先谈一下并查集：它是一种动态维护不重叠集合的做法，并且支持查询和合并的数据结构，是超级有用的；
1、find函数：查询某一个元素属于哪个集合；
2.union函数：将两个集合合并为一个大集合；
//代码效果参考：http://www.jhylw.com.cn/155924389.html
使用一个树形结构储存每一个集合，树上的节点表示一个元素，树根是代表集合，father数组表示当前i的父亲节点，初始化数组为本身，每次递归寻找根节点；
这样，合并的时候我们可以找到两棵树的树根，并且father【root1】=root2;就完成了操作；
并查集有压缩路径和按秩合并；
1.压缩路径：在每次执行find是将访问的节点直接指向树根；均摊复杂度O（logN）；
2.按秩合并：秩表示的是树的深度（未压缩路径时），秩也可以表示集合的大小，每次合并是将秩小的元素合并到秩较大的元素上，只增加查询小的结构的代价，只使用按秩合并，复杂度：O（logN）；
但同时使用可以将复杂度降到常数级别（不会写）；
int find(int x)
{
if(x==father【x】) return x;
else return father【x】=find(father【x】);
}
void Union(int x,int y)
{
int p=find(x),q=find(y);
if(p!=q) father【p】=q;
}
当然find函数可以使用符号运算符；
int find(int x){return x==father【x】?x:father【x】=find(father【x】);}
这样你就可以写洛谷的并查集模板了；
模板；
#include
using namespace std;
#define N 500001
templateinline void read(T &x)
{
x=0;T f=1,ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
x*=f;
}
int n,m,f【N】;
inline int find(int x)
{
if(x!=f【x】)
f【x】=find(f【x】);
return f【x】;
}
inline void Union(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
f【fx】=fy;
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;i++)
f【i】=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
read(x);read(y);read(z);
if(x==1)
{
int p=find(y),q=find(z);
f【q】=p;
}
else
{
if(find(y)==find(z)) cout["Y"[endl;
else cout["N"[endl;
}
}
return 0;
}
View Code
今天想谈三道题需要将并查集的思想拓展：
关押罪犯
学长的题解：二分+2-SAT 先预处理出所有的v，然后离散化一下，在那个的基础上二分，对于每次二分出的值约束边权超过所二分出的边权的两点。
还有二分图，嗯，不会嗯，那我们来看看并查集怎么处理这道题；
第一种思路：
我们可以建立两个集合，那么初始化也要注意是2*n了，一个集合表示这两个人不在一个监狱里，另一个集合表示这两个人在一个监狱里面，那么我们就可以将所有的怒气值从大到小进行一个排序，然后进行枚举，查找他们所在的集合，然后判断是不是出现了冲突（在同一个集合里面），如果出现了冲突，那么这个值就是怒气值的最大值，直接输出就好，如果没有出现冲突，那么将这两个放在一个并查集（表示不在同一个监狱的并查集）里面，表示这两个人是在不同的监狱里面。然后继续循环。
其实这道题就是运用到了并查集的容斥原理，和一点小小的贪心，我们将尽量怒气值比较大的放在不同的监狱里面，然后放次大的，如果出现冲突，也就是说在前面的安排之下，没有办法将当前的两个人分开，那么这两个人只能在一个监狱里面，这也就是最小的怒气值。
看代码：
#include
using namespace std;
#define N 500001
templateinline void read(T &x)
{
x=0;T f=1,ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
x*=f;
}
int n,m,d【N】,f【N】;
struct pink
{
int x,y,v;
}a【N[1】;
bool mycmp(pink x,pink y)
{
return x.v>y.v;
}
int find(int x)
{
return f【x】==x?x:f【x】=find(f【x】);
}
int main()
{
int flag=0;
read(n);read(m);
for(int i=1;i<=m;i++)
{
read(a【i】.x);read(a【i】.y);read(a【i】.v);
}
for(int i=1;i<=2*n;i++) f【i】=i;
sort(a+1,a+m+1,mycmp);
for(int i=1;i<=m;i++)
{
int x,y;
x=a【i】.x,y=a【i】.y;
int xx=find(a【i】.x);
int yy=find(a【i】.y);
if(xx==yy)
{
cout[a【i】.v[endl;
return 0;
}
f【yy】=find(a【i】.x+n);
f【xx】=find(a【i】.y+n);
}
puts("0");
return 0;
}
View Code
第二种思路：
可能发生冲突，所以尽量属于不同的监狱，就是属于不同的集合，怒气值越大，我们可以尽量让他们让他们属于不同的集合，如果在从大到小的安排之下不得已需要让两个人在一个集合，所以直接输出当前答案；敌人的敌人是可以放到同一个集合里的；
两种思路其实是一样的，我们用的是并查集维护一种关系；
那么：
#include
using namespace std;
#define N 500001
templateinline void read(T &x)
{
x=0;T f=1,ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
x*=f;
}
int n,m,d【N】,f【N】;
struct pink
{
int x,y,v;
}a【N[1】;
bool mycmp(pink x,pink y)
{
return x.v>y.v;
}
int find(int x)
{
return f【x】==x?x:f【x】=find(f【x】);
}
int main()
{
int flag=0;
read(n);read(m);
for(int i=1;i<=m;i++)
{
read(a【i】.x);read(a【i】.y);read(a【i】.v);
}
for(int i=1;i<=n;i++)
f【i】=i;
sort(a+1,a+m+1,mycmp);
for(int i=1;i<=m;i++)
{
int x,y;
x=a【i】.x,y=a【i】.y;
if(find(x)==find(y))
{
printf("%d\n",a【i】.v);
flag=1;
break;
}
else
{
if(!d【x】) d【x】=y;
else
{
int p=find(d【x】);
f【p】=find(y);
}
if(!d【y】) d【y】=x;
else
{
int q=find(d【y】);
f【q】=find(x);
}
}
}
if(!flag) printf("%d\n",0);
return 0;
}
View Code
2.银河英雄传
这是一个带权的并查集啦；
我们用一个d数组表示到根节点距离，size数组表示集合大小；
find和Union稍作修改；
inline int find(int x)
{
if(x==father【x】) return x;
int root=find(father【x】);//递归寻找集合代表；
d【x】+=d【father【x】】;//求出边权和；return father【x】=root;//压缩路径；
}
void Union(int x,int y)
{
int p=find(x),q=find(y);
father【p】=q;
d【p】=size【q】;
size【q】+=size【p】;
}
当接受到c命令是查询，如果根节点相同，那么就是同一列，不同则不是；d数组分别记录x，y到跟节点，然后他们之间的abs(d【x】-d【y】)-1;就是距离；
如果是M命令，合并即可，我们还需要用一个size数组记录集合大小；
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include[span style="color: rgba(0, 0, 255, 1)">set]
#include
#include
#include
#include
#include[span style="color: rgba(0, 0, 255, 1)">string]
#include
#include
#include
#include
using namespace std;
#define N 1000001
templateinline void read(T &x)
{
x=0;T f=1,ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
x*=f;
}
int n,x,y,father【N】,d【N】,size【N】;
inline int find(int x)
{
if(x==father【x】) return x;
int root=find(father【x】);
d【x】+=d【father【x】】;
father【x】=root;
return father【x】=root;
}
void Union(int x,int y)
{
int p=find(x),q=find(y);
father【p】=q;
d【p】=size【q】;
size【q】+=size【p】;
}
int main()
{
for(int i=1;i<=N;i++)
father【i】=i,d【i】=0,size【i】=1;
read(n);
for(int i=1;i<=n;i++)
{
char c;
cinc;
read(x);read(y);
if(c=='M') Union(x,y);
else if(c=='C')
{
int p=find(x),q=find(y);
if(p!=q)
{
cout["-1"[endl;
}
else
{
printf("%d\n",abs(d【x】-d【y】)-1);
}
}
}
return 0;
}
View Code
3.食物链
这种传递关系只用一次并查集显然维护不了，所以我们可以考虑使用并查集的拓展域；
把每个动物x拆成三个点，同类域xself，捕食域xeat，天敌域xenemy；
如果x吃y，那么换句话讲，x的捕食域是y的同类，x的同类是y的天敌，x的天敌是y的捕食域，因为为环形关系；
如果x和y是同类，x的天敌和y的天敌是一类，x的捕食域和同类和y分别都一样；
合并就完事了；
判断谎言（flam）
与x和y是同类矛盾：
1.xeat和yself是一个集合；
2.xself和yeat是一个集合；
与x吃y矛盾：
1.xself和yself在一个集合；
2.xself和yeat在一个集合；
