本文共 965 字，大约阅读时间需要 3 分钟。

今天我看了并查集的内容。

并查集是一种支持合并与查询的数据结构，简单来说，主要包含两步操作：

2.Merge，把两个集合合并成一个大集合。

操作中，主要采用“代表元”法，即为每一个集合选择一个固定的元素，作为整个集合的代表。

形象的，把并查集看作一个森林，是用一棵树存储每个集合，书上的每一个节点都是一个元素，树根是集合的代表元素。

为了提高效率，又引入了路径压缩与按秩合并两种思想。

代码具体实现说明：

1.并查集的存储

使用一个数组fa保存父节点（根的父节点设为自己）

int fa[size]；

2.初始化

设有n个元素，起初所有元素各自构成一个独立的集合，即有n颗1个节点的数。

for(int i=1;i<=n;i++)

fa[i]=i;

3.并查集的Get操作

若x是树根，则x就是集合代表，否则递归访问fa[x]直至根节点。

int get(x){  if(x==f[x])     return x;else   return fa[x]=get(fa[x]);//路径压缩，fa直接赋值为代表元素 }

4.Merge操作

合并元素x和元素y所在的集合，等价于让x的树根作为y的树根的子节点。void merge(int x,int y){  fa[get(x)]=get(y);}

再就是“扩展域”与“边带权”的并查集

用一个数组d，用d[x]保存节点x到父节点fa[x]之间的边权，

在路径压缩后，每个访问过的节点都会直接指向树根，我们同时更新这些点的d值，就可以利用路径压缩来统计每个节点到树根之间路径上的一些信息。

在某些问题中，传递关系不止一种，能够互相导出，此时它就有了用武之地。

Get操作int get(int x){  if(x==fa[x]) return x;  int root=get(fa[x]);//递归计算集合代表  d[x]+=d[fa[x]];//对边权求和  return fa[x]=root;//路径压缩}

size 数组在每个树根上记录集合大小。void merge(int x,int y){  x=get(x);  y=get(y);  fa[x]=y;  d[x]=size[y];  size[y]+=size[x];}

转载地址：http://cmyzi.baihongyu.com/