import java util ArrayList public class Test public static void main S

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
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++;
}
}
}
}