并查集

export function useUnionFind(n) {
    const parent = new Array(n).fill(0).map((_, i) => i)
    const size = new Array(n).fill(1)
    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x])
        return parent[x]
    }
    function union(x, y) {
        let rx = find(x)
        let ry = find(y)
        if (rx === ry) return false
        if (size[rx] > size[ry]) [rx, ry] = [ry, rx]
        parent[rx] = ry
        size[ry] += size[rx]
        return true
    }
    function isUnion(x, y) {
        return find(x) === find(y)
    }
    function setSize(x) {
        return size[find(x)]
    }
    return {
        union,
        find,
        isUnion,
        setSize,
    }
}

pub struct UnionFind {
    parent: Vec<usize>,
    size: Vec<usize>,
    groups: usize,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        let parent = (0..n).collect::<Vec<usize>>();
        let size = vec![1; n];
        Self {
            parent,
            size,
            groups: n,
        }
    }

    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }

    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (mut rx, mut ry) = (self.find(x), self.find(y));
        if rx == ry {
            return false;
        }
        self.groups -= 1;
        if self.size[rx] > self.size[ry] {
            std::mem::swap(&mut rx, &mut ry);
        }
        self.parent[rx] = ry;
        self.size[ry] += self.size[rx];
        true
    }
}

class UnionFind {

    int[] parent, size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    /**
     * 合并两个节点所在的集合
     *
     * @param x 待合并的一个节点
     * @param y 待合并的另一个节点
     * @return null
     */
    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) { // 在同一个集合中
            return false;
        }
        if (size[rootX] > size[rootY]) { // 按秩合并，优化时间
            int t = rootX;
            rootX = rootY;
            rootY = t;
        }
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
        return true;
    }

    public boolean isUnion(int x, int y) {
        return find(x) == find(y);
    }

    /**
     * 查找根节点
     *
     * @param x 待查找的节点
     * @return 返回根节点
     */
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
}

package algo

type UnionFind struct {
    parent []int
    size   []int
    groups int
}

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := range n {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{
        parent: parent,
        size:   size,
        groups: n,
    }
}

func (this *UnionFind) Find(x int) int {
    if this.parent[x] != x {
        this.parent[x] = this.Find(this.parent[x])
    }
    return this.parent[x]
}

func (this *UnionFind) Union(x, y int) {
    rx, ry := this.Find(x), this.Find(y)
    if rx == ry {
        return
    }
    this.groups--
    if this.size[rx] > this.size[ry] {
        rx, ry = ry, rx
    }
    this.parent[rx] = ry
    this.size[ry] += this.size[rx]
}

func (this *UnionFind) IsUnion(x, y int) bool {
    return this.Find(x) == this.Find(y)
}

func (this *UnionFind) Groups() int {
    return this.groups
}