java">import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class UnionFind<T> {/*** 如果sets[i] < 0，那么第i个元素为根元素，且sets[i]的绝对值为集合大小* 否则，第i个元素为非根元素，set[i]的值为其父亲元素的索引*/private int[] sets;/*** 反向索引，记录的是当前元素在sets中的索引*/private Map<T, Integer> reverseIndexMap;/*** 根据elems元素内容创建一个并查集* * @param elems*/public UnionFind(T[] elems) {sets = new int[elems.length];Arrays.fill(sets, -1);reverseIndexMap = new HashMap<>();for (int i = 0; i < elems.length; i++) {reverseIndexMap.put(elems[i], i);}}/*** 返回元素e所在集合的标识* * @param e* @return*/public int find(T e) {Deque<Integer> stack = new LinkedList<>();int eIndex = reverseIndexMap.get(e);while (sets[eIndex] >= 0) {int fIndex = sets[eIndex];stack.push(eIndex);eIndex = fIndex;}// 这里进行路径压缩while (!stack.isEmpty()) {sets[stack.pop()] = eIndex;}return eIndex;}/*** 将e1所在元素集合与e2所在元素集合合并* * @param e1* @param e2*/public void union(T e1, T e2) {if (isSameSet(e1, e2)) {// 如果已经处于同一个集合了，那么不进行合并return;}int f1Index = find(e1);int f2Index = find(e2);// 因为f1和f2是根节点，所以对应的sets中的元素为// 二者所在集合大小的相反数int size1 = Math.abs(sets[f1Index]);int size2 = Math.abs(sets[f2Index]);if (size1 < size2) {sets[f2Index] += sets[f1Index];sets[f1Index] = f2Index;} else {sets[f1Index] += sets[f2Index];sets[f2Index] = f1Index;}}/*** 如果e1和e2处于同一个集合中，那么返回true，否则返回false* * @param e1* @param e2* @return*/public boolean isSameSet(T e1, T e2) {return find(e1) == find(e2);}private void debug() {System.out.println(Arrays.toString(sets));}public static void main(String[] args) {String[] nums = { "1", "2", "3", "4", "5", "6" };UnionFind<String> uf = new UnionFind<>(nums);uf.union(nums[0], nums[1]);uf.union(nums[3], nums[4]);uf.debug();uf.union(nums[0], nums[4]);uf.find(nums[4]);uf.debug();}
}