GabWiki

Appearance

并查集 ​

路径压缩优化的并查集 ​

模板题：合并集合

Java
class UnionFind {
    private int[] root;
    
    public UnionFind(int size) {
        root = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        root[find(p)] = find(q);
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
class UnionFind {
    private int[] root;
    
    public UnionFind(int size) {
        root = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        root[find(p)] = find(q);
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
C++
class UnionFind {
private:
    int* root;

public:
    UnionFind(int size) : root(new int[size]) {
        for (int i = 0; i < size; ++i) root[i] = i;
    }

    int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    void join(int p, int q) {
        root[find(p)] = find(q);
    }
    
    bool is_connected(int p, int q) {
        return find(p) == find(q);
    }
};
class UnionFind {
private:
    int* root;

public:
    UnionFind(int size) : root(new int[size]) {
        for (int i = 0; i < size; ++i) root[i] = i;
    }

    int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    void join(int p, int q) {
        root[find(p)] = find(q);
    }
    
    bool is_connected(int p, int q) {
        return find(p) == find(q);
    }
};

基于路径压缩的按秩合并优化的并查集 ​

Java
class UnionFind {
    private int[] root;
    private int[] rank;
    
    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootP] > rank[rootQ]) root[rootQ] = rootP;
        else {
        	root[rootP] = rootQ;
            if (rank[rootP] == rank[rootQ]) ++rank[rootP];
        }
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
class UnionFind {
    private int[] root;
    private int[] rank;
    
    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootP] > rank[rootQ]) root[rootQ] = rootP;
        else {
        	root[rootP] = rootQ;
            if (rank[rootP] == rank[rootQ]) ++rank[rootP];
        }
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
C++
class UnionFind {
private:
    int* root;
    int* rank;

public:
    UnionFind(int size) : root(new int[size]), rank(new int[size]) {
        for (int i = 0; i < size; ++i) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    void join(int p, int q) {
        int root_p = find(p), root_q = find(q);
        if (root_p == root_q) return;
        if (rank[root_p] > rank[root_q]) root[root_q] = root_p;
        else {
        	root[root_p] = root_q;
            if (rank[root_p] == rank[root_q]) ++rank[root_p];
        }
    }
    
    bool is_connected(int p, int q) {
        return find(p) == find(q);
    }
};
class UnionFind {
private:
    int* root;
    int* rank;

public:
    UnionFind(int size) : root(new int[size]), rank(new int[size]) {
        for (int i = 0; i < size; ++i) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    void join(int p, int q) {
        int root_p = find(p), root_q = find(q);
        if (root_p == root_q) return;
        if (rank[root_p] > rank[root_q]) root[root_q] = root_p;
        else {
        	root[root_p] = root_q;
            if (rank[root_p] == rank[root_q]) ++rank[root_p];
        }
    }
    
    bool is_connected(int p, int q) {
        return find(p) == find(q);
    }
};

统计连通分量的综合并查集 ​

Java
class UnionFind {
    public int groups;
    private int[] root;
    private int[] rank;
    
    public UnionFind(int size) {
        groups = size;
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootP] > rank[rootQ]) root[rootQ] = rootP;
        else {
        	root[rootP] = rootQ;
            if (rank[rootP] == rank[rootQ]) ++rank[rootP];
        }
        --groups;
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
class UnionFind {
    public int groups;
    private int[] root;
    private int[] rank;
    
    public UnionFind(int size) {
        groups = size;
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) root[i] = i;
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootP] > rank[rootQ]) root[rootQ] = rootP;
        else {
        	root[rootP] = rootQ;
            if (rank[rootP] == rank[rootQ]) ++rank[rootP];
        }
        --groups;
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

维护每个集合大小的并查集 ​

模板题：连通块中点的数量

Java
class UnionFind {
    private int[] roots, sizes;
    
    public UnionFind(int size) {
        roots = new int[size];
        for (int i = 0; i < size; ++i) {
            roots[i] = i;
            sizes[i] = 1;
        }
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rp = find(p), rq = find(q);
        if (rp != rq) {
            root[rp] = rq;
        	sizes[rq] += sizes[rp];
        }
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
class UnionFind {
    private int[] roots, sizes;
    
    public UnionFind(int size) {
        roots = new int[size];
        for (int i = 0; i < size; ++i) {
            roots[i] = i;
            sizes[i] = 1;
        }
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        int rp = find(p), rq = find(q);
        if (rp != rq) {
            root[rp] = rq;
        	sizes[rq] += sizes[rp];
        }
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

维护每个节点到根节点距离的并查集 ​

Java
class UnionFind {
    private int[] roots, dists;
    
    public UnionFind(int size) {
        roots = new int[size];
        for (int i = 0; i < size; ++i) {
            roots[i] = i;
            dists[i] = 0;
        }
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        roots[find(p)] = find(q);
        dists[find(p)] = distance; // 根据具体问题，初始化find(a)的偏移量
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
class UnionFind {
    private int[] roots, dists;
    
    public UnionFind(int size) {
        roots = new int[size];
        for (int i = 0; i < size; ++i) {
            roots[i] = i;
            dists[i] = 0;
        }
    }
    
    public int find(int n) {
        return n == root[n] ? n : (root[n] = find(root[n]));
    }

    public void union(int p, int q) {
        roots[find(p)] = find(q);
        dists[find(p)] = distance; // 根据具体问题，初始化find(a)的偏移量
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

反集 ​

作用 ​

并查集反集用来储存并查集维护集合性质相反（互斥）的集合。

并查集的反集适用于只有元素只有两种性质的题目，也就是说，这个元素不属于并查集维护集合，则其必定属于另一个集合。

原理 ​

如果要将两个性质相斥的元素 a,b 合并，可以用并查集合并 union(a+n,b),union(b+n,a) （ a+n 相当于 a 的虚拟敌人， union(a+n,b) 相当于把 b 和 a 的虚拟敌人合并， union(b+n,a) 同理）。再之，如果 a 与 c 的性质互斥，合并 union(a+n,c),union(c+n,a) ，此时 b 与 c 性质相同，它们也成功合并在了一起（此时并查集中： {{a,b+n,c+n},{b,a+n,c}} ）。

实现方式 ​

在初始化并查集时初始化两倍于数据范围大小的并查集，超出数据范围部分称为反集。

经典应用 ​

判二分图。