完整代码：并查集

并查集逻辑结构

并查集顾名思义：逻辑结构 – 集合；操作 – 合并 & 查找

如：有两个集合 A{1，7，9，10}，B{2，5，8，11}，现有以下问题：

1、判断元素9在哪个集合内

2、合并A，B集合

要解决上述两个问题，首先得思考 集合（各元素划分到互不相交的子集） 应该以何种方式存储到计算机中。

联想到森林的定义：m棵互不相交的树的集合，这不正好适用嘛？如图：

逻辑关系已成，那么用什么存储方式呢？考虑到并查集主要是两个操作 – 查某元素在哪个子集里 & 合并两集合（从根处合并）。那就需要频繁找双亲，树的双亲表示法应该是最佳的。

---

存储类型表示 – 双亲表示法

用一个（结构体）数组，结点数据成员：data + parent（下标）

#include<string>
typedef std::string UElemType;

// 结点
typedef struct
{
    /* data */
    UElemType data;
    int parent;
}UFSetNode;

// 并查集
#define MAXNODE 100
typedef struct
{
    UFSetNode Node[MAXNODE];
    // // 或者动态分配
    // UFSetNode *Node;    // 初始化: Set.Node = new UFSetNode[Set.size];
    int size;   // 记录结点数
}UFSet;

---

操作

下面为了更直观的展示，结点内只存 parent下标

#define MAXNODE 100
int UFSets[MAXNODE];

初始化

每个元素均构造一棵树组成森林，parent全存 -1 即可。

void InitUFSet(int S[]){
    for(int i = 0; i < MAXNODE; i++)
        S[i] = -1;
}

---

并（集合A∪集合B）

根结点合并，如：A并到B内，则将A的根结点的parent改成B的根结点下标即可。

void Union(int S[], int Root1, int Root2){
    // 原本为一个集合内
    if(Root1 == Root2) return;

    // 将 R1 并到 R2
    else S[Root1] = Root2;
}

---

查（元素 -> 子集）

元素A一直找祖宗，直到找到根结点返回即可

int Find(int S[], int x){
    while(S[x] >= 0) x = S[x];
    return x;
}

---

分析查操作的最坏时间复杂度

查的最坏时间复杂度和树高有关，与合并操作下树的增长速度有关。如图：

因此：需要对合并操作进行优化

---

优化

合并优化：小树合并到大树，查的最坏时间复杂度O(logn)

如何知道两棵树哪个结点最多呢？一个可行的方案是将根结点的parent存放 结点数的负值（该方案极容易实现，因为初始化时parent = -1 -> |parent| = 1 – 即为当前树的结点值 – 只有根节点，因此只要比较两个根节点的parent绝对值 + 维护大树根结点的parent值即可）

// 小树合并到大树
void Union(int S[], int Root1, int Root2){
    if(Root1 == Root2) return;
    // Root1 parent绝对值 > Root2 -> Root1是大树，Root2 合并到 Root1
    if(S[Root1] < S[Root2]){
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }else{
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
}

查找优化：压缩路径 查的最坏时间复杂度O(α(n)¹)

优化的目标：降低树的高度，那么最理想的结果：集合除根节点外其他结点全部挂在根节点下；

若一直进行合并操作形成如图所示的树：

现要进行查找操作，压缩过程（沿路结点直接挂到根节点下）如下：

int Find(int S[], int x){
    int root = x;
    // 找到子集的根节点
    while(S[root] >= 0) root = S[root];
    // 沿路节点全部挂到根节点下
    while(x != root){
        int tmp = S[x];  // 记录双亲结点
        S[x] = root;     // 沿路结点直接挂到根节点
        x = tmp;
    }
    return root;
}

---

1. 备注：α(n)为增长速度极慢的函数，对于常见的n，通常a(n) <= 4 (最坏时间复杂度为常数级) ↩︎