并查集

定义

---

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

并查集支持两个操作：

• 查询（Find）：判断两个元素是否属于同一集合
• 合并（Union）：合并两个元素所属集合

初始化

初始时，每个元素都是一个单独的集合。方便起见，将每个元素的父亲设为自己。

struct UnionFind  
{  
    vector<int> parent; // 父节点  
    explicit UnionFind(const int size) : parent(size)  
    {  
        iota(parent.begin(), parent.end(), 0); // 初始化父节点, parent[i] = i  
    }  
};

查询

找到当前节点的根节点。

路径压缩

因为查询的结果为根节点，如果当前节点不是根节点或根节点的子节点，就将当前节点直接到根节点，这样下次查询就可以不用再查找了。

实现

struct UnionFind  
{  
    vector<int> parent; // 父节点
    int find(const int x)  
    {  
        if (parent[x] == x)  
            return parent[x];  
        return parent[x] = find(parent[x]); // 路径压缩  
    }  
};

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

启发式合并

合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将秩（即深度）较小的树连到另一棵，以免发生退化。

实现

struct UnionFind  
{  
    vector<int> parent; // 父节点  
    vector<int> rank; // 秩  
    void unite(int x, int y)  
    {  
        x = find(x), y = find(y);  
        if (x == y)  
            return;  
        if (rank[x] > rank[y])  
        {  
            parent[y] = x;  
            rank[x] += rank[y];  
        }  
        else  
        {  
            parent[x] = y;  
            rank[y] += rank[x];  
        }  
    }  
};

模版

typedef struct {  
    vector<int> parent; // 父节点  
    vector<int> rank; // 秩  
    explicit UnionFind(const int size) : parent(size), rank(size, 1)  
    {  
        iota(parent.begin(), parent.end(), 0); // 初始化父节点, parent[i] = i  
    }  
  
    int find(const int x)  
    {  
        if (parent[x] == x)  
            return parent[x];  
        return parent[x] = find(parent[x]); // 路径压缩  
    }  
  
    void unite(int x, int y)  
    {  
        x = find(x), y = find(y);  
        if (x == y)  
            return;  
        if (rank[x] > rank[y])  
        {  
            parent[y] = x;  
            rank[x] += rank[y];  
        }  
        else  
        {  
            parent[x] = y;  
            rank[y] += rank[x];  
        }  
    }  
} UnionFind;

带权并查集

在普通并查集的基础上，维护节点到父节点的边权。

struct WeightedUnionFind  
{  
    vector<int> parents; // 父节点  
    vector<int> weight; // 权重，规定weight[x] - weight[root] = value ， weight[root] = 0  
    explicit WeightedUnionFind(const int size) : parents(size + 1), weight(size + 1)  
    {  
        iota(parents.begin(), parents.end(), 0); // 初始化父节点, parent[i] = i  
    }  
  
    int find(const int x)  
    {  
        if (parents[x] != x)  
        {  
            const int parent = parents[x]; // weight[x] = value (x -> parent)  
			parents[x] = find(parent); // 路径压缩，保证 weight[parent] = value' (parent -> root)
			weight[x] += weight[parent]; // weight[x] = value + value' (x -> parent -> root)  
        }  
        return parents[x];  
    }  
  
    void unite(const int x, const int y, const int value)  
    {  
        const int fx = find(x), fy = find(y);  
        if (fx == fy)  
            return;  
        parents[fx] = fy;  
        // 因为weight[x] + weight[fx] - weight[y] = value （x -> fx -> fy -> y）  
        // 所以weight[fx] = weight[y] - weight[x] + value  
        weight[fx] = weight[y] - weight[x] + value;  
    }  
  
    int different(const int x, const int y)  
    {  
        if (find(x) != find(y)) // 不在同一集合  
            return -1;  
        return weight[x] - weight[y];  
    }  
};