首页  思维导图  详情

查并集算法

2021-08-02 09:42:38   0  举报





仅支持查看

AI智能生成

查并集

作者其他创作

大纲/内容

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

并查集的重要思想在于，用集合中的一个元素代表集合。

并查集理解比喻

把集合比喻成帮派，而代表元素则是帮主。接下来我们利用这个比喻，看看并查集是如何运作的。

1. 所有大侠一开始各自为战。他们各自的帮主自然就是自己。
（对于只有一个元素的集合，代表元素自然是唯一的那个元素）

2. 现在1号和3号比武，假设1号赢了（这里具体谁赢暂时不重要），那么3号就认1号作帮主
（合并1号和3号所在的集合，1号为代表元素）。

3. 现在2号想和3号比武（合并3号和2号所在的集合），但3号表示，别跟我打，让我帮主来收拾你（合并代表元素）。
不妨设这次又是1号赢了，那么2号也认1号做帮主。

4. 现在我们假设4、5、6号也进行了一番帮派合并，江湖局势变成下面这样：

5. 现在假设2号想与6号比，跟刚刚说的一样，喊帮主1号和4号出来打一架（帮主真辛苦啊）。
1号胜利后，4号认1号为帮主，当然他的手下也都是跟着投降了。

6. 经过不断合并得到一个树状的结构，要寻找集合的代表元素，只需要一层一层往上访问父节点，直达树的根节点

并查集实现

初始化

int fa[MAXN];
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
fa[i] = i;
}

假如有编号为1, 2, 3, ..., n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。
一开始，我们先将它们的父节点设为自己。

查询

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

我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。
要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

合并

inline void merge(int i, int j)
{
fa[find(i)] = find(j);
}

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。

优化

合并（路径压缩）

int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

把沿途的每个节点的父节点都设为根节点

按秩合并

例如我们需要合并集合7和集合8

设置谁为帮主是会影响树深度的

初始化

inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

我们用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。

合并

inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

合并时比较两个根节点，把rank较小者往较大者上合并。