import java.util.ArrayList;
public class Test
{
public static void main(String[] args)
{
ArrayList<Element<String>> set1 = new ArrayList<Element<String>>();
set1.add(new Element<String> ("alpha"));
set1.add(new Element<String> ("beta"));
set1.add(new Element<String> ("gamma"));
set1.add(new Element<String> ("delta"));
set1.add(new Element<String> ("epsilon"));
ArrayList<Element<String>> set2 = new ArrayList<Element<String>>();
set2.add(new Element<String> ("ah"));
set2.add(new Element<String> ("be"));
set2.add(new Element<String> ("ve"));
set2.add(new Element<String> ("ge"));
set2.add(new Element<String> ("de"));
set2.add(new Element<String> ("eh"));
for (int i = 0; i < set1.size()-1; i++) {
set1.get(i).union(set1.get(i+1));
}
for (int i = 0; i < set2.size()-1; i++) {
set2.get(i).union(set2.get(i+1));
}
for (Element<String> a : set1) {
for (Element<String> b : set1) report(a, b);
}
for (Element<String> a : set2) {
for (Element<String> b : set2) report(a, b);
}
for (Element<String> a : set1) {
for (Element<String> b : set2) report(a, b);
}
set1.get(0).union(set2.get(0));
for (Element<String> a : set1) {
for (Element<String> b : set2) report(a, b);
}
}
private static <T> void report(Element<T> a, Element<T> b)
{
System.out.println("" + a.x() + "=" + b.x() + ": " + a.equivalent(b));
}
}
class Element<T> {
private T x;
private int depth = 0;
private Element<T> parent = this;
// Создаёт новый элемент со значением x
public Element(T x) {
this.x = x;
}
// Возвращает значение элемента
public T x() {
return this.x;
}
private Element<T> find(){
if(this.parent == this) return this;
else{
this.parent = this.parent.find();
}
return this.parent;
}
// Определяет, принадлежит ли текущий элемент
// тому же множеству, что и элемент elem
public boolean equivalent(Element<T> elem) {
return this.find() == elem.find();
}
// Объединяет множество, которому принадлежит текущий
// элемент, с множеством, которому принадлежит
// элемент elem
public void union(Element<T> elem) {
Element<T> root_x = this.find(), root_y = elem.find();
if(root_x.depth < root_y.depth){
root_x.parent = root_y;
}
else{
root_y.parent = root_x;
if(root_x.depth == root_y.depth && root_x != root_y){
root_x.depth++;
}
}
}
}