lets-go-coding
  • 并查集 (union & find) 是一种树型的数据结构，用于处理⼀些不交集(Disjoint Sets)的合并及查询问题。
  • Find:确定元素属于哪一个⼦集。它可以被用来确定两个元素是否属于同⼀子集。
  • Union:将两个⼦集合并成同一个集合。

在生活中的例子

  1. ⼩弟 —> ⽼大
  2. 帮派识别
  3. 两种优化⽅式

并查集代码

function MakeSet(x)
    x.parent : = x

function Find(x)
    if x.parent == x
        return x
    else
        return Find(x.parent)

function Union(x, y)
    xRoot : = Find(x)
    yRoot : = Find(y)
    xRoot.parent := yRoot

并查集优化一

function MakeSet(x)
    x.parent := x
    x.rank := 0

function Union(x, y)
    xRoot := Find(x)
    yRoot := Find(y)
    if xRoot == yRoot
        return

    // x 和 y 不在同一个集合，合并他们
    if xRoot.rank < yRoot.rank
        xRoot.parent := yRoot
    else if xRoot.rank > yRoot.rank
        yRoot.parent := xRoot
    else
        yRoot.parent := xRoot
        xRoot.rank := xRoot.rank + 1

并查集优化二

Java 实现路径压缩

public clas QuickUnionUF {
    private int[] roots;

    public QuickUnionUF(int N) {
        roots = new int[N];
        for (int i =0; i < N; i++) {
            roots[i] = i;
        }
    }

    private int findRoot(int i) {
        int root = i;
        while (root != roots[root])
            root = roots[root];
        while (i != roots[i]) {
            int tmp = roots[i]; roots[i] = root; i = tmp;
        }
        return root;
    }

    public boolean connected(int p, int q) {
        return findRoot(p) == findRoot(q);
    }

    public boolean connected(int p, int q) {
        return findRoot(p) == findRoot(q);
    }

    public boolean connected(int p, int q) {
        return findRoot(p) == findRoot(q);
    }

    public void union(int p, int q) {
        int qroot = findRoot(q);
        int proot = findRoot(p);
        roots[proot] = qroot;
    }
}

实战题⽬

  1. https://leetcode.com/problems/number-of-islands/
  2. https://leetcode.com/problems/friend-circles/
Last Updated: 9/27/2019, 5:01:51 PM

← 字典和散列表基础→