并查集的理解

印象里大学里面似乎没有讲过这个数据结构。就这个数据结构本身而言，其实是不难的。实际在应用到算法题中的时候，难点在于把实际的问题映射到这种数据结构，如果完成了这种映射，那么，解题就轻而易举了。

最终的并查集的实现，一般只有最经典的一种。

在 理解的过程中，我们可以从第一、第二个版本迭代过去。

版本一

下面是最基础朴素的版本，

/**
 * 最基础版本的并查集
 */
public class UnionFind {
  // 记录连通分量
  private int count;
  // 节点 x 的父节点是 parent[x]
  private int[] parent;

  // 构造函数，n 为图的节点总数
  public UnionFind(int n) {
    // 一开始互不连通
    this.count = n;
    // 指向父节点的指针一开始指向自己
    parent = new int[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }

  // 返回某个节点 x 的根节点
  private int find(int x) {
    while (parent[x] != x) {
      x = parent[x];
    }
    return x;
  }

  // 把 p 和 q 连通起来
  public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) {
      return;
    }
    // 将两棵树合并成一棵
    parent[rootP] = rootQ;
    count--; // 两个分量合二为一
  }

  // 返回当前的连通分量个数
  public int count() {
    return count;
  }

  public boolean connected(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
  }
}

版本二

下面是有了一点简单的优化的版本，

/**
 * 使用 size 来优化，在主要是在连通两棵树的时候有选择地去连接
 */
public class UnionFind {
  // 记录连通分量
  private int count;
  // 节点 x 的父节点是 parent[x]
  private int[] parent;
  // 记录树的重量
  private int[] size;

  // 构造函数，n 为图的节点总数
  public UnionFind(int n) {
    // 一开始互不连通
    this.count = n;
    // 指向父节点的指针一开始指向自己
    parent = new int[n];
    // 最初，每一棵树都只有一个节点，所以每一棵树的初始值都应该是 1
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      size[i] = 1;
    }
  }

  // 返回某个节点 x 的根节点
  private int find(int x) {
    while (parent[x] != x) {
      x = parent[x];
    }
    return x;
  }

  // 把 p 和 q 连通起来
  public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) {
      return;
    }
    // 将两棵树合并成一棵，并且，要使小树连在大树上面，这样会比较平衡
    if (size[rootP] > size[rootQ]) {
      parent[rootQ] = rootP;
      size[rootP] += size[rootQ];
    } else {
      parent[rootP] = rootQ;
      size[rootQ] += size[rootP];
    }
    count--; // 两个分量合二为一
  }

  // 返回当前的连通分量个数
  public int count() {
    return count;
  }

  public boolean connected(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
  }
}

版本三

下面是使用了路径压缩的版本，那个递归的方法(函数)很简单，但是非常巧妙，

/**
 * 这里是使用路径压缩来处理(递归)，这里 size 其实就没有什么必要了，直接去掉
 */
public class UnionFind {
  // 记录连通分量
  private int count;
  // 节点 x 的父节点是 parent[x]
  private int[] parent;

  // 构造函数，n 为图的节点总数
  public UnionFind(int n) {
    // 一开始互不连通
    this.count = n;
    // 指向父节点的指针一开始指向自己
    parent = new int[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }

  // 返回某个节点 x 的根节点
  // 路径压缩，压缩得很彻底，最终除了根节点，所有节点都是指向那唯一一个根节点
  private int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  // 把 p 和 q 连通起来
  public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);

    if (rootP == rootQ) {
      return;
    }
    // 将两棵树合并成一棵，并且，要使小树连在大树上面，这样会比较平衡
    parent[rootQ] = rootP;

    count--; // 两个分量合二为一
  }

  // 返回当前的连通分量个数
  public int count() {
    return count;
  }

  public boolean connected(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
  }
}