>cat UnionFindDemo.java
import java.util.*;
import java.io.*;
public class UnionFindDemo {
public static String[] names = {"John", "Ben", "Miller", "Shao", "Yohi", "Eva", "Keith",
"Mooshy", "Dave", "Yin", "Charlse", "Emma"};
public static String[][] friends = {{"John", "Ben"}, {"John", "Miller"},
{"Yohi", "Mooshy"}, {"Eva", "Ben"}};
private static List<Integer> ids = new ArrayList<>();
private static Map<String, Integer> unions = new HashMap<>();
private static Map<Integer, Integer> size = new HashMap<>();
private int root(int i) {
while(ids.get(i) != i) {
ids.set(i, ids.get(i)); //pass compression
i = ids.get(i);
}
return i;
}
public void union(String name1, String name2) {
int v = unions.get(name1.trim()).intValue();
int root1 = root(v); //lgN
int size1 = size.computeIfAbsent(root1, key -> 1);
v = unions.get(name2.trim()).intValue();
int root2 = root(v);
int size2 = size.computeIfAbsent(root2, key -> 1);
//balance
if(size1 >= size2) {
ids.set(root2, root1);
size.put(root1, size.get(root1) + size.get(root2));
} else {
ids.set(root1, root2);
size.put(root2, size.get(root1) + size.get(root2));
}
}
public boolean isConnected(String name1, String name2) {
if(name1 == null || name2 == null || unions.get(name1.trim()) == null || unions.get(name2.trim()) == null) {
return false;
}
int v = unions.get(name1.trim()).intValue();
int root1 = root(v);
v = unions.get(name2.trim()).intValue();
int root2 = root(v); //lgN
return root1 == root2;
}
public static void main(String...args) throws IOException {
for(int i = 0; i < names.length; i++) {
unions.put(names[i], i);
ids.add(i, i);
}
UnionFindDemo uf = new UnionFindDemo();
for(int i = 0; i < friends.length; i++) {
uf.union(friends[i][0], friends[i][1]);
}
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//name, name
String[] pairs = in.readLine().split(",");
System.out.println(unions);
System.out.println(ids);
System.out.println(uf.isConnected(pairs[0], pairs[1]));
}
}
>javac UnionFindDemo.java
>java UnionFindDemo
John, Eva
{Eva=5, Mooshy=7, Keith=6, Shao=3, Miller=2, John=0, Ben=1, Dave=8, Yohi=4, Charlse=10, Emma=11, Yin=9}
[0, 0, 0, 3, 4, 0, 6, 4, 8, 9, 10, 11]
true
>java UnionFindDemo
John, Yohi
{Eva=5, Mooshy=7, Keith=6, Shao=3, Miller=2, John=0, Ben=1, Dave=8, Yohi=4, Charlse=10, Emma=11, Yin=9}
[0, 0, 0, 3, 4, 0, 6, 4, 8, 9, 10, 11]
false
>
