@@ -0,0 +1,1325 @@
+import java.util.Arrays;%0A%0Apublic class UnionFind %7B%0A%0A%09private static Node%5B%5D set;%0A%0A%09private static void union(Node x, Node y) %7B%0A%09%09Node x_root = find(x);%0A%09%09Node y_root = find(y);%0A%09%09if (x_root == y_root)%0A%09%09%09return;%0A%0A%09%09// x and y are not already in same set. Merge them.%0A%09%09if (x_root.rank %3C y_root.rank)%0A%09%09%09x_root.parent = y_root;%0A%09%09else if (x_root.rank %3E y_root.rank)%0A%09%09%09y_root.parent = x_root;%0A%09%09else %7B%0A%09%09%09y_root.parent = x_root;%0A%09%09%09x_root.rank++;%0A%09%09%7D%0A%09%7D%0A%0A%09private static Node find(Node x) %7B%0A%09%09if (x.parent != x)%0A%09%09%09x.parent = find(x.parent);%0A%09%09return x.parent;%0A%09%7D%0A%0A%09public static void main(String%5B%5D args) %7B%0A%09%09final int n = 10;%0A%0A%09%09set = new Node%5Bn%5D;%0A%09%09for (int i = 0; i %3C n; i++)%0A%09%09%09set%5Bi%5D = new Node(i);%0A%0A%09%09int%5B%5D%5B%5D pairs = %7B %7B 1, 2 %7D, %7B 3, 1 %7D, %7B 3, 5 %7D, %7B 4, 6 %7D, %7B 5, 4 %7D,%0A%09%09%09%09%7B 4, 3 %7D, %7B 5, 2 %7D, %7B 2, 1 %7D, %7B 7, 10 %7D, %7B 9, 10 %7D, %7B 8, 9 %7D %7D;%0A%09%09for (int i = 0; i %3C pairs.length; i++) %7B%0A%09%09%09int a = pairs%5Bi%5D%5B0%5D - 1;%0A%09%09%09int b = pairs%5Bi%5D%5B1%5D - 1;%0A%0A%09%09%09union(set%5Ba%5D, set%5Bb%5D);%0A%09%09%7D%0A%09%09%0A%09%09System.out.println(Arrays.toString(set));%0A%09%7D%0A%0A%09private static class Node %7B%0A%09%09private Node parent;%0A%09%09private int rank, index;%0A%0A%09%09private Node(int index) %7B%0A%09%09%09rank = 0;%0A%09%09%09this.index = index;%0A%09%09%09parent = this;%0A%09%09%7D%0A%0A%09%09public String toString() %7B%0A%09%09%09Node n = this;%0A%09%09%09while (n.index != n.parent.index)%0A%09%09%09%09n = n.parent;%0A%09%09%09return %22%22 + n.index;%0A%09%09%7D%0A%09%7D%0A%0A%7D%0A

Create UnionFind.java