并查集

作者: siliconx | 来源:发表于2021-01-25 09:11 被阅读0次

markdown学习
算法模板(四)并查集
并查集入门使用
并查集练习
并查集
数据结构与算法（十二）并查集(Union Find)
并查集
并查集
并查集
并查集

1. 概念

并查集主要用于解决一些元素分组的问题，管理一系列不相交的集合，并支持两种操作：
• 查询（Find）：查询两个元素是否在同一个集合中；
• 合并（Union）：把两个不相交的集合合并为一个集合。
并查集一般用于集合、无向图，一般情况下不适用于有向图（但也有例外Leetcode 685. 冗余连接II）。

2. 标准模板：

Java:

class DSU {
    private int components;  // 连通分量的个数
    private int[] parent;  // 根节点

    public DSU(int n) {
        components = n;
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

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

        return parent[x];
    }

    public void merge(int a, int b) {
        int ap = find(a);
        int bp = find(b);
        if (ap != bp) {
            --components;
            parent[bp] = ap;
        }
    }

    public int getComponents() {
        return components;
    }
}

C++:

class DSU {
private:
    int components;  // 记录连通分量的个数
    vector<int> parent;  // 记录每个节点的根节点

public:
    DSU(int n) {
        parent.resize(n);
        components = n;
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        // 查找x的根节点
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x, int y) {
        // 合并两个连通分量
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            --components;
            parent[fx] = fy;
        }
    }

    int getComponents() {
        return components;
    }
};

Python:

class DSU(object):
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]

    def merge(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        if ap != bp:
            self.parent[bp] = ap