一.个人理解
1. 并查集的概念
并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。
2.主要包括三个操作
- 初始化
将每个点所在集合初始化成本身
- 查找根结点
- 合并
3.主要应用的问题
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
这里我们可以试着处理一下这个问题
判断下图中是否存在环（或者可以说下图是否是一个树）
**根节点：
一个节点的祖宗为他的根节点
父节点：
与这个点直接相连的点为父节点**
这里用并查集就非常好理解
根据这个图，我们逐个边来看
- 第一条边：3连接1
1和3在同一个集合
- 第二条边：4连接2
2和4在同一个集合
- 第三条边：2连接1
1和2在同一个集合，这时候我们就需要合并上面的两个小集合，成为大集合。
假设现在没有那一条红色的线
那么我们现在可以看出来图中没有环
如果我们把图中1当作根节点
那么
-
2的父节点是1，根节点是1；
- 3的父节点是2，根节点是1；
- 4的父节点是2，根节点是1。
这时如果我们把红线加到除了刚才已经连接的位置的任何位置，如果出现了，连接的两个点的根节点相同那么就一定出现了环
如图中4和2之间的红线，根节点都为1我们该如何实现这个操作呢
我们现需要做的有三步- 初始化
- 查找根结点
- 合并
首先我们需要一个数组来存储每个节点的根节点
这时候就先假设每个点都是独立的点，也就是说每个点的根节点都是他自己
所以并查集就出现了三个重要的函数
- init()
- root_find()
- merge()
int d[N];//定义储存根节点
void init()
{
for(int i=0; i<N; i++)
d[i]=i;//初始化为根节点都是本身
}
int root_find(int x)//查找节点x的根节点
{
if(x==d[x])//如果根节点是本身
return x;
else
{
int root=root_find(d[x]);
return root;
}
}
int merge(int x,int y)
{
int rx=root_find(x);
int ry=root_find(y);
if(rx!=ry)
{
d[rx]=ry;
return 1;//可以合并
}
return 0;//不可以合并
}二.并查集的两种优化方式
1.路径压缩
如果我们的树是这样
可以看出来非常长，相当于一个链表了，这时候时间复杂度就是logn,
可是如果它变成这样就非常好，我们可以一次找到根节点
因为合并和找根节点没有直接关系
实现这个操作我们只需要在原来代码上改动一个步骤
int root_find(int x)//查找节点x的根节点
{
if(x==d[x])//如果根节点是本身
return x;
else
{
int root=root_find(d[x]);
//return root;//在这里
return d[x]=root;
}
}2.按秩合并
秩是线性代数术语。在线性代数中，一个矩阵的秩是其非零子式的最高阶数，一个向量组的秩则是其最大无关组所含的向量个数。
这里我们可以认为是树的高度
如果我们将这两个树合并的时候会有两种情况：
- 将较低的树最为根节点
可以看出树的高度增加了，这就说明如果这样合并树的高度会一直增加。
- 将较高的树最为根节点
可以看出来高度还是4
所以按秩合并就是用较高的树作为根节点进行合并
如果两个树的高度相同那么就任意找一个树作为根节点，然后这个树的高度加一
因为合并和找根节点没有关系，所以代码实现就是在合并函数中做一些改动
int h[N];//记录高度
int merge(int x,int y)
{
int rx=root_find(x);
int ry=root_find(y);
if(rx!=ry)
{
if(h[rx]>h[ry])
{
d[ry]=rx;
h[ry]=h[rx];
}
else if(h[rx]<h[ry])
{
d[rx]=ry;
h[rx]=h[ry];
}
else
{
d[rx]=ry;
h[yx]++;
}
return 1;//可以合并
}
return 0;//不可以合并
}