并查集基础

一、概念及其介绍

并查集是一种树型结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。

对于并查集主要支持两个操作：

• 并{ union(p,q) }
• 查找{ find(p) }
• 来回答一个问题：

连接{ inConnected(p, q) }

二、并查集的基本数据表示

难点分析：横向上的数值其实是对应横线下数据的在数组中的索引值，也就是说横线下是一个真正的数组，而横线上则是数组对应的索引，在这里我们是用索引当作元素，用数组数据值的异同来表示元素是否连接。

横线上：用数组索引表示元素

横线下：表示连接情况(值为0的表示在一个集合即连接)

所以0-4在同一个集合，5-9在同一个集合：

三、代码实现

下面我们来介绍并查集的主要操作：

我们先实现一个并查集：

#include <iostream>
#include <cassert>
using namespace std;
// 我们的第一版Union-Find
namespace UF1 
{
    class UnionFind 
    {
        private:
        int *id;         // 第一版Union-Find本质就是一个数组 
        int count;     // 数据个数 
        public:// 构造函数 
        UnionFind(int n) 
        {
            count = n;
            id = new int[n];
            // 初始化, 每一个id[i]指向自己, 没有合并的元素,每一个数都是一个集合 
            for (int i = 0; i < n; i++)
                id[i] = i;
            }
        }
        // 析构函数~ 
        UnionFind() 
        {
            delete[] id;
        }
    }
}

1. find的实现：(查询元素所在的集合编号，直接返回数组值，O(1) 的时间复杂度。)

// 查找过程, 查找元素p所对应的集合编号
int find(int p) {assert(p >= 0 && p < count);return id[p];
}

1. isConnected的实现：

// 查看元素p和元素q是否所属一个集合
// O(1)复杂度
bool isConnected(int p, int q) 
{
   return find(p) == find(q);
}

1. union的实现：(合并元素 p 和元素 q 所属的集合， 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并，这个过程是 O(n) 复杂度。)

// 合并元素p和元素q所属的集合
// O(n) 复杂度
void unionElements(int p, int q) 
{   
    //union在c++中是一个关键字，所以这里用 unionElements 
    int pID = find(p);
    int qID = find(q);
    if (pID == qID)return;
    // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
    for (int i = 0; i < count; i++)
        if (id[i] == pID)
            id[i] = qID;
}