并查集初步

引言

有若干节点，并将其中一些节点对进行连接，要判断任意两个节点是否连通（有路径到达，而不要求直接连接），连通后就不会断开连通关系，此时就可以使用并查集。并查集擅长动态维护许多具有传递性的关系，能在无向图中维护节点之间的连通性。

要判断两个节点是否连通，可以把连通的节点加入到各自的集合里，也就是，同一个集合里的节点都是连通的，不同集合里的节点是不连通的。

如图，节点a、b、c、d属于同一个集合，它们之间是连通的；节点x、y、z属于同一个集合，它们之间也是连通的。但是，不同集合里的节点，如b和x，是不连通的。

可以发现，每个集合构成了树形的结构，同一个集合里的节点，它们的根节点是相同的。要判断两个节点是否连通，只需要判断它们的根节点是否一致即可。

并查集的API定义：

class UF {
public:
    // 查找节点的根节点
    int find(int x) {};
    // 连接节点p和q
    void join(int x, int y) {};
    // 判断两个节点是否连通
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    };
};

实现

并查集的存储结构可以使用数组或链表，一般采用数组作为实现的方式。数组记录元素的父节点。例如，A[i] = j，表示节点i的父节点是节点j。

初始时，每个节点各自作为一个集合，也就是节点的父节点是自身。

private:
    vector<int> parent;
public:
    UF(int n) {
        for (int i = 0; i < n; i++) {
            parent.push_back(i);
        }
    }

查找节点的根节点时，如果节点的父节点是自身，那么该节点就是根节点。否则，顺着父节点不断向上找，直至根节点。

int find(int x) {
    return parent[x] == x ? x : find(parent[x]);
}

连接两个节点时，实际上就是把两个节点的所在的集合合并成一个。首先需要找到两个节点的根节点，把其中一个根节点的父节点修改为另一个根节点。

void join(int x, int y) {
    parent[find(x)] = find(y);
}

路径压缩

对于 find 的过程，可以修改节点的父节点来加速下次查找，这个优化称为“路径压缩”。

例如，在查找根节点的过程中，修改沿途节点的父节点为根节点：

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

非递归的写法：

int find(int x) {
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    int tmp;
    while (x != root) {
        tmp = parent[x];
        parent[x] = root;
        x = tmp;
    }
    return x;
}

还有其它的路径压缩方式。例如，在查找根节点的过程中，若节点不是根节点，就将节点的父节点修改为爷节点（父节点的父节点）：

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

合并策略

对于 join 的过程，如果不加任何策略合并，可能会形成很长的路径，应该尽量选择深度更小的集合的根节点进行父节点的修改。

按秩合并

集合的秩，也就是集合所对应的树的深度。

如果两个集合的秩不相等，就把秩小的集合的根节点的父节点修改为秩大的集合的根节点。如果两个集合的秩相等，那么，将其中一个集合的根节点的父节点修改为另一个集合的根节点，同时，将未修改父节点的根节点的集合的秩+1。

class UF {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UF(int n) {
        for (int i = 0; i < n; i++) {
            parent.push_back(i);
            rank.push_back(1);
        }
    }

    void join(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot != yRoot) {
            if (rank[xRoot] > rank[yRoot]) {
                parent[yRoot] = xRoot;
            } else {
                parent[xRoot] = yRoot;
                if (rank[xRoot] == rank[yRoot]) {
                    rank[yRoot]++;
                }
            }
        }
    }
    ...

也可以在根节点存储秩的信息，思路参考下面的“按size合并”

按size合并

为了记录集合的size，也就是集合包含节点的个数，可以将根节点的父节点的值修改为“-1*集合包含节点的个数”，同时，根节点的判断方式修改为父节点的值小于0。合并时，将节点数少的集合并入节点数多的集合，也就是修改节点数少的集合的根节点的父节点为节点数多的集合的根节点。注意，在修改父节点前要更新节点数多的集合的节点数。

class UF {
private:
    vector<int> parent;
public:
    UF(int n) {
        for (int i = 0; i < n; i++) {
            parent.push_back(-1);
        }
    }

    int find(int x) {
        return parent[x] < 0 ? x : parent[x] = find(parent[x]);
    }

    void join(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot != yRoot) {
            if (parent[xRoot] < parent[yRoot]) {
                parent[xRoot] += parent[yRoot];
                parent[yRoot] = xRoot;
            } else {
                parent[yRoot] += parent[xRoot];
                parent[xRoot] = yRoot;
            }
        }
    }
    ...

不过，按size合并的策略并不总能选择深度更小的集合的根节点进行父节点的修改，例如本文第一个图的情况。