写在前面

并查集（Union-Find）算法是一个专门针对「动态连通性」的算法。连通指的是一种等价关系：自反性、对称性、传递性。并查集算法提供的API可以有很多操作：将两个节点连通、判断两节点是否连通或者有多少个连通分量等。

Union-Find 算法实现

Union-Find 算法的关键就在于 union 和 connected 函数的效率。我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。

  • 写成类的形式：
    • 根节点数组、连通分量计数（options）
    • 初始化函数：构造数组记录初始根节点（自身）
    • 连接函数：如果二者不连通，则将其中一个的根节点接到另一个的根节点上
    • 判断是否连接：计算各自根节点进行比较
    • 查找根节点函数：压缩路径的最好方法（递归），避免树的不平衡。

初始化状态

对于初始化状态时，所有节点都是不连通的，各自指向的都是自己

class UF {
    // 记录连通分量
    private:
        int count;
        // 节点 x 的父节点是 parent[x]
        int* parent;
    public:
        /* 构造函数，n 为图的节点总数 */
        UF(int n) {
            // 一开始互不连通
            this->count = n;
            // 父节点指针初始指向自己
            parent = new int[n];
            for (int i = 0; i < n; i++)
                parent[i] = i;
        }
        /* 其他函数 */
};

连接两个节点

让其中的（任意）一个节点的根节点接到另一个节点的根节点上（注意这里是根节点接到另一个根节点上）

void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ)
        return;
    // 将两棵树合并为一棵
    parent[rootP] = rootQ;
    // parent[rootQ] = rootP 也一样
    count--; // 两个分量合二为一
}

判断节点是否连通

根据parent数组计算各自的根节点，相等则说明二者是连通的，反之则是不连通的。

bool connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

路径压缩、find函数

find 主要功能就是从某个节点向上遍历到树根，其时间复杂度就是树的高度。因此，尽可能的保持树比较低，每次访问的时间复杂度也就低。

  • 其实我们并不在乎每棵树的结构长什么样，只在乎根节点。

  • 精妙的递归写法：那个递归过程中把路径上的所有结点的父节点都设置为根结点。也就是先找到最根节点，然后把这条路径上的节点都接到根节点，每个子树高度都是1了。

    int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

优化思路总结

来自labuladong

  1. 用 parent 数组记录每个节点的父节点，相当于指向父节点的指针，所以 parent 数组内实际存储着一个森林（若干棵多叉树）。

  2. 用 size 数组记录着每棵树的重量，目的是让 union 后树依然拥有平衡性，保证各个 API 时间复杂度为 $O(logN)$，而不会退化成链表影响操作效率。

  3. 在 find 函数中进行路径压缩，保证任意树的高度保持在常数，使得各个 API 时间复杂度为 O(1)。使用了路径压缩之后，可以不使用 size 数组的平衡优化。

对应到题目

990. 等式方程的可满足性

  • 先把所有相等的连通起来，再判定那些不连通的，根据判断结果返回。

    class UF {
private:
vector<int> parent;
public:
// 构造函数
UF(int n) {
    for(int i=0;i<n;i++) {
        parent.push_back(i);
    }
}
// 连通两个点
void union_(int x,int y) {
    int rootX=find(x);
    int rootY=find(y);
    if(rootX==rootY)
        return;
    parent[rootX]=rootY;  // 是把它的根节点接到另一个上面
}
// 判断是否连通
bool isconnected(int x,int y) {
    int rootX=find(x);
    int rootY=find(y);
    if(rootX==rootY) {
        return true;
    }
    return false;
}
// 查找根节点
int find(int x) {
    if(parent[x]!=x){
        parent[x]=find(parent[x]);
    }
    return parent[x];
}
};

class Solution {
public:
bool equationsPossible(vector<string>& equations) {
    UF uf(26); // 26个字母
    vector<int> flag;
    // 空间换时间
    for(int i=0;i<equations.size();i++) {
        flag.push_back(i);
        if(equations[i][1]=='=') {
            uf.union_(equations[i][0]-97,equations[i][3]-97);
            flag.pop_back();
        }
    }
    for(auto s:flag){
        int x=equations[s][0]-97,y=equations[s][3]-97;
        if(uf.isconnected(x,y)){
            return false;
        }
    }   
    return true;
}
};

$\cdots$ end $\cdots$