Union Find (Disjoint Set)

并查集: 一种用来解决集合查询/合并的数据结构 支持O(1) find / O(1) union操作

A very good source for Union Find:

Princeton CS Algorithms 4th Edition: https://algs4.cs.princeton.edu/15uf/


Union Find: 一种用于支持集合快速合并查找操作的数据结构

  • O(1)合并两个集合- Union

  • O(1)查询元素所属集合- Find

基本数据结构是:使用哈希表或者数组来存储每个节点父亲节点

并查集可以干什么? What Union Find Can Do?

  1. 判断在不在同一个集合中
    • find 操作
  2. 关于集合合并
    • union 操作

并查集应用场景总结:

1.合并两个集合

2.查询某个元素所在集合

3.判断两个元素是否在同一个集合

4.获得某个集合的元素个数

5.统计当前集合个数

并查集的操作 Union Find - Operation

查询 Find (递归? 非递归?)

模板代码

HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

int find(int x) {
    int parent = x;
    while (parent ! = father.get(parent)) {
        parent = father.get(parent);
    }
    return parent;
}

合并 Union

老大哥之间合并
跟小弟没关系

HashMap<Integer, Integer> father = new HashMap<Integer. Integer>();

void union(int x, int y) {
    int fa_x = find(x);
    int fa_y = find(y);
    if (fa_x != fa_y) {
        father.put(fa_x, fa_y);
    }
}

并查集完整模板 Union Find Template

HashMap Based

class UnionFind {
    UnionFind() {}
    HashMap<Integer, Integer> father = new HashMap<Integer. Integer>();
    int find(int x) {
        int parent = x;
        while (parent ! = father.get(parent)) {
            parent = father.get(parent);
        }
        return parent;
    }
    void union(int x, int y) {
        int fa_x = find(x);
        int fa_y = find(y);
        if (fa_x != fa_y) {
            father.put(fa_x, fa_y);
        }
    }
}

Array Based

Weighted quick-union with path compression

https://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html

public class WeightedQuickUnionPathCompressionUF {
    private int[] parent;  // parent[i] = parent of i
    private int[] size;    // size[i] = number of sites in tree rooted at i
                           // Note: not necessarily correct if i is not a root node
    private int count;     // number of components

    /**
     * Initializes an empty union–find data structure with {@code n} sites
     * {@code 0} through {@code n-1}. Each site is initially in its own 
     * component.
     *
     * @param  n the number of sites
     * @throws IllegalArgumentException if {@code n < 0}
     */
    public WeightedQuickUnionPathCompressionUF(int n) {
        count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    /**
     * Returns the number of components.
     *
     * @return the number of components (between {@code 1} and {@code n})
     */
    public int count() {
        return count;
    }


    /**
     * Returns the component identifier for the component containing site {@code p}.
     *
     * @param  p the integer representing one site
     * @return the component identifier for the component containing site {@code p}
     * @throws IllegalArgumentException unless {@code 0 <= p < n}
     */
    public int find(int p) {
        validate(p);
        int root = p;
        while (root != parent[root])
            root = parent[root];
        while (p != root) {
            int newp = parent[p];
            parent[p] = root;
            p = newp;
        }
        return root;
    }

   /**
     * Returns true if the the two sites are in the same component.
     *
     * @param  p the integer representing one site
     * @param  q the integer representing the other site
     * @return {@code true} if the two sites {@code p} and {@code q} are in the same component;
     *         {@code false} otherwise
     * @throws IllegalArgumentException unless
     *         both {@code 0 <= p < n} and {@code 0 <= q < n}
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    // validate that p is a valid index
    private void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));  
        }
    }  

    /**
     * Merges the component containing site {@code p} with the 
     * the component containing site {@code q}.
     *
     * @param  p the integer representing one site
     * @param  q the integer representing the other site
     * @throws IllegalArgumentException unless
     *         both {@code 0 <= p < n} and {@code 0 <= q < n}
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // make smaller root point to larger one
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count--;
    }

    /**
     * Reads in a sequence of pairs of integers (between 0 and n-1) from standard input, 
     * where each integer represents some site;
     * if the sites are in different components, merge the two components
     * and print the pair to standard output.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        int n = StdIn.readInt();
        WeightedQuickUnionPathCompressionUF uf = new WeightedQuickUnionPathCompressionUF(n);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

}
Another Weighted + Path Compression - Simpler Version
public class UnionFind {
        int[] parent;
        int[] rank;
        int cnt;

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

        public boolean union(int a, int b) {
            int pa = find(a);
            int pb = find(b);
            if (pa == pb) return false;
            cnt--;
            if (rank[pa] < rank[pb]) {
                parent[pa] = pb;
            } else {
                parent[pb] = pa;
                if (rank[pa] == rank[pb]) rank[pa]++;
            }
            return true;
        }

        public int find(int a) {
            while (a != parent[a]) {
                parent[a] = parent[parent[a]];
                a = parent[a];
            }
            return a;
        }
    }

results matching ""

    No results matching ""