union find

Union Find Implementation。

UF class interface

1
2
3
4

public class UF
    UF(int N)
    int find(int i)
    void union(int i, int j)

M union find operation on N objects:

• quick find: O(MN) (worst case)
• quick union: O(MN) (worst case)
• path-compressed weighted quick union: O(N + MlgN) ~ linear time
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

  class WeightedUF { int[] id; int[] size; public WeightedUF(int n) { id = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { id[i] = i; size[i] = 1; } } public int find(int i) { if (id[i] != i) { id[i] = find(id[i]); // path compression } return id[i]; } public void union(int i, int j) { i = find(i); j = find(j); if (i == j) return; if (size[i] < size[j]) { // small tree is put under the big tree id[i] = j; size[j] += size[i]; } else { id[j] = i; size[i] += size[j]; } } }