UnionFind
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
public class UnionFind {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
UnionFind(HashSet<Integer> set) {
for (Integer i : set) {
map.put(i, i);
}
}
UnionFind(int[] array) {
for (int i = 0; i < array.length; i++) {
map.put(array[i], array[i]);
}
}
UnionFind(ArrayList<Integer> array) {
for (Integer i : array) {
map.put(i, i);
}
}
public int find(int x) {
int parent = map.get(x);
while (parent != map.get(parent)) {
parent = map.get(parent);
}
int father = map.get(x);
while (father != map.get(father)) {
int temp = map.get(father);
map.put(father, parent);
father = temp;
}
return parent;
}
public void union(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if (root_x != root_y) {
map.put(root_x, root_y);
}
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
}
Generic
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
public class UnionFind<Item> {
Map<Item, Item> map = new HashMap<Item, Item>();
UnionFind(HashSet<Item> set) {
for (Item i : set) {
map.put(i, i);
}
}
UnionFind(Item[] array) {
for (int i = 0; i < array.length; i++) {
map.put(array[i], array[i]);
}
}
UnionFind(ArrayList<Item> array) {
for (Item i : array) {
map.put(i, i);
}
}
public Item find(Item x) {
Item parent = map.get(x);
while (parent != map.get(parent)) {
parent = map.get(parent);
}
Item father = map.get(x);
while (father != map.get(father)) {
Item temp = map.get(father);
map.put(father, parent);
father = temp;
}
return parent;
}
public void union(Item x, Item y) {
Item root_x = find(x);
Item root_y = find(y);
if (root_x != root_y) {
map.put(root_x, root_y);
}
}
public boolean connected(Item p, Item q) {
return find(p) == find(q);
}
}