Union-Find

public class UnionFind {
  int[] root, rank;

  public UnionFind(int size) {
    this.root = new int[size];
    this.rank = new int[size];
    for (int i = 0; i < size; i++) {
      root[i] = i;
      rank[i] = 1;
    }
  }

  public int find(int x) { // Path compression optimization
    if (x == root[x]) return x;
    return root[x] = find(root[x]);
  }

  public void union(int x, int y) { // Union by rank optimization
    int rootX = find(x), rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] > rank[rootY]) root[rootY] = rootX;
      else if (rank[rootY] > rank[rootX]) root[rootX] = rootY;
      else {
        root[rootY] = rootX;
        rank[rootX]++;
      }
    }
  }

  public boolean connected(int x, int y) {
    return find(x) == find(y);
  }
}

• Used when dealing with connected components.