import java.util.*;
import java.io.*;
import java.nio.charset.Charset;
import java.nio.file.*;
public class QuickUnion {
public static final int NNames = 10;
public static final int NConn = 5;
//use your own implementation of Map and List if you like
private static Map<String, Integer> unions = new HashMap<>();
private static List<Integer> ids = new ArrayList<>();
private static Map<Integer, Integer> size = new HashMap<>();
private int root(String name) {
if(name == null ||unions.get(name.trim()) == null) {
return -1;
}
int v = unions.get(name.trim()).intValue();
while(ids.get(v) != v) {
ids.set(v, ids.get(ids.get(v))); //pass compression
v = ids.get(v);
}
return v;
}
public void union(String name1, String name2) {
int v1 = root(name1);
int v2 = root(name2);
int count1 = size.computeIfAbsent(v1, key -> new Integer(1));
int count2 = size.computeIfAbsent(v2, key -> new Integer(1));
//balance tree for lgN performance
if(count1 >= count2) {
ids.set(v2, v1);
size.put(v1, v1 + size.get(v2));
} else {
ids.set(v1, v2);
size.put(v2, v2 + size.get(v1));
}
}
public boolean isConnected(String name1, String name2) {
int v1 = root(name1);
int v2 = root(name2);
return v1 > 0 && v2 > 0 && v1 == v2;
}
private static void makeNames(int N, int M) {
try(BufferedWriter w = new BufferedWriter(new FileWriter("names"));) {
for(int i = 0; i < N; i++) {
w.write("name" + i);
w.newLine();
ids.add(i, i);
}
w.flush();
} catch(IOException e) {
e.printStackTrace();
}
try(BufferedWriter w = Files.newBufferedWriter(Paths.get("friends"), Charset.forName("US-ASCII"))) {
Random r = new Random();
for(int i = 0; i < M; i++) {
w.write("name" + r.nextInt(M) + ", " + "name" + r.nextInt(M));
w.newLine();
}
w.flush();
} catch (IOException e1) {
e1.printStackTrace();
}
}
public static void main(String[] args) throws IOException {
makeNames(NNames, NConn);
try(BufferedReader r = new BufferedReader(new FileReader("names"))) {
String l;
int c = 0;
while( (l = r.readLine()) != null) {
unions.put(l.trim(), c++);
}
} catch(Exception e) {
e.printStackTrace();
}
QuickUnion qu = new QuickUnion();
Files.lines(Paths.get("friends")).forEach(
i -> {String[] pairs = i.split(","); qu.union(pairs[0], pairs[1]);}
);
System.out.println(unions);
System.out.println(ids);
System.out.flush();
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
String l;
while(!(l = r.readLine()).equals("end")) {
assert l.contains(","): "wrong input";
String[] pairs = l.split(",");
boolean a = qu.isConnected(pairs[0], pairs[1]);
System.out.println(a);
System.out.flush();
}
}
}
