并查集

引言

前几天做leetcode周赛有道题解了许久，sky告诉我一种新的数据结构可以快速干掉那题，并查集。特来学习一下，本文中我讲介绍基础到经过路径压缩的并查集。

一种数据结构，在这个数据结构中，相同的集合拥有相同的标签，不同的集合标签不同。用来元素分组问题，支持两种不同类型的操作：

合并（union）：把两个元素所在的集合合并为一个集合
查询（find）：查询元素所属的集合

初始化

初始时所有元素都归属于单独的一个集合，最常见的一种初始化方式是fa[x]=x

1
2
3
4
5
6


vector<int> fa;
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa.push_back(i);
}

对于这段代码，c++有另一个函数可以实现上述功能。

iota函数对一个范围数据进行赋值：

1
2
3
4
5
6
7
8
9


template <class ForwardIterator, class T>
  void iota (ForwardIterator first, ForwardIterator last, T val)
{
  while (first!=last) {
    *first = val;
    ++first;
    ++val;
  }
}

iota版本

1
2
3
4
5
6


vector<int> fa;
inline void init(int n)
{
    fa.resize(n);
    iota(fa.begin(), fa.end(), 0);
}

原始版查询、合并

查询

1
2
3
4
5
6
7


int F(int x)
{
    if(fa[x] == x)
        return x;
    else
        return F(fa[x]);
}

合并

1
2
3
4


inline void U(int i, int j)
{
    fa[F(i)] = F(j);
}

这个版本有个缺点，在合并的过程中fa只记录了节点的父亲节点，但是我们要找到根节点来代表这个集合，因此只能不断的向上找，直到找到根节点。有什么办法对次进行优化的吗？

路径压缩

这个思路比较直接。既然每次递归调用问父节点，直到父节点发现自己的父节点是自己，从而结束递归，那么在函数自底向上逐个返回之前，在当前节点记录下根节点。这有个形象的比喻：既然每次找的时候父亲都会不断的递归问父亲你知不知道祖宗是谁？如果他发现就是自己，那么就会向他的儿子回复祖宗是我，他的儿子向儿子的儿子说祖宗是ｘ。那么在儿子告诉儿子的儿子的时候记住祖宗是谁不就行了吗？以后谁再问祖宗是谁，该节点表示早就在其他人问的时候就记住了。

查询

1
2
3


int F(int x) {
  return x == ids[x] ? x : (ids[x] = F(x));
}

合并

1
2
3


void U(int i, int j) {
  ids[F(i)] = ids[F(j)];
}

这个版本在每次递归查询的时候都会把根节点的值赋值给递归调用路径上的所有节点。

扩展练习

547. 省份数量 - 力扣（LeetCode）
1722. 执行交换操作后的最小汉明距离 - 力扣（LeetCode）

参考

Union Find – Kyle’s Blog
算法学习笔记（１）：并查集－Pecco的知乎