P242 实现并查集

描述#

这个题目说的是，你要实现一个并查集，其中包含 find 和 union 两个方法。find(x) 用于查找元素 x 属于哪个集合，你需要返回集合内的一个代表元素。union(x, y) 用于合并元素 x 和元素 y 所在的两个集合。注意：为了方便起见，集合中的元素使用非负整数来表示。

代码#

public class AlgoCasts {

  public class UnionFind {

    private int[] parent, size;

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

    private int findRecursive(int x) {
      if (parent[x] == x) return x;
      return findRecursive(parent[x]);
    }

    private int findPathCompressionRecursive(int x) {
      if (parent[x] == x) return x;
      parent[x] = findPathCompressionRecursive(parent[x]);
      return parent[x];
    }

    private int findIterative(int x) {
      int root = x;
      while (parent[root] != root)
        root = parent[root];
      return root;
    }

    private int findPathCompressionIterative(int x) {
      int root = x;
      while (parent[root] != root)
        root = parent[root];
      while (parent[x] != root) {
        int tmp = parent[x];
        parent[x] = root;
        x = tmp;
      }
      return root;
    }

    public int find(int x) {
      return findPathCompressionIterative(x);
    }

    public void union(int x, int y) {
      int xRoot = find(x);
      int yRoot = find(y);
      if (xRoot == yRoot) return;
      if (size[xRoot] < size[yRoot]) {
        parent[xRoot] = yRoot;
        size[yRoot] += size[xRoot];
      } else {
        parent[yRoot] = xRoot;
        size[xRoot] += size[yRoot];
      }
    }

  }

}