题目

题目

5995. 字符串分组

class UF {
    int[] p, r;
    int setCount;

    public UF(int n) {
        this.setCount = n;
        this.p = new int[n];
        this.r = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
            r[i] = 1;
        }
    }

    public int find(int x) {
        // 路径压缩
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    public boolean merge(int x, int y) {
        int xx = find(x), yy = find(y);
        if (xx == yy) return false;
        if (r[xx] >= r[yy]) {
            p[yy] = xx;
            r[xx] += (r[xx] - r[yy]);
        } else {
            r[xx] = yy;
        }
        setCount--;
        return true;
    }
}