并查集

• 一般用于快速判断两个元素是否同属于一个集合
• 数组形式表示树结构
• 插入元素会被映射到从0开始的顺序整数中

实现技巧

• 路径压缩：在find时，通过递归并返回找到的祖宗节点并赋值，可以达成find后降低树高的功效
• 按秩归并：在unite时，其中一方会挂在另一方的门下，所以希望“小的挂到大的上面”，以此来产生结果高度更小的树，有两种方式：
  • 高度：树高：S[Root]=-树高，代码多一步判断：即：两个树相同高度时，增加树高
  • 数目（推荐）：S[Root]=-元素个数。子孙节点数目，可以通过利用根节点来达成，根节点之前是-1，现在改为-n，其中n是包含根节点的整个树的节点数目

LC.990

class UF {
public:
    UF(int _n) :count(_n), parent(_n, -1) {}
    int getCount() { return count; }
    bool isConnected(int a, int b) {
        int class1 = find(a);
        int class2 = find(b);
        return class1 == class2;
    }
    void unite(int a, int b) {
        int class1 = find(a);
        int class2 = find(b);
        if (class1 == class2)
            return;
        if (parent[class1] < parent[class2]) { // 按秩归并
            parent[class1] += parent[class2];
            parent[class2] = class1;
        }
        else {
            parent[class2] += parent[class1];
            parent[class1] = class2;
        }
        --count;
    }

private:
    int find(int pos) {
        if (parent[pos] < 0)
            return pos;
        return parent[pos] = find(parent[pos]); // 路径压缩
    }

    int count;
    vector<int> parent;
};

// leetcode 990
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UF a(26);
        for (int i = 0; i < equations.size(); i++) {
            if (equations[i][1] == '=') {
                a.unite(equations[i][0] - 97, equations[i][3] - 97);
            }
        }
        for (int i = 0; i < equations.size(); i++) {
            if (equations[i][1] == '!') {
                if (a.isConnected(equations[i][0] - 97, equations[i][3] - 97))
                    return false;
            }
        }
        return true;
    }
};