并查集算法

简单实现了Quick-Union的并查集(增加了path compression)。还有Quick-Find, Weighted Quick-union, Weighted Quick-union With Path Compression. 参考https://blog.csdn.net/dm_vincent/article/details/7655764

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class UnionFind {
   int[] parent;

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

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

   void union(int x, int y) {
      parent[find(x)] = find(y);
   }
}