并查集

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素

合并（Union）：合并两个元素所属集合（合并对应的树）
查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class UnionSet<V> {

    Map<V, V> parentMap;
    Map<V, Integer> sizeMap;

    public UnionSet(List<V> list) {
        parentMap = new HashMap<>(list.size());
        sizeMap = new HashMap<>(list.size());
        for (V v : list) {
            parentMap.put(v, v);
            sizeMap.put(v, 1);
        }
    }

    public V findHead(V v) {
        Stack<V> stack = new Stack<>();
        while (v != parentMap.get(v)) {
            stack.push(v);
            v = parentMap.get(v);
        }
        while (!stack.isEmpty()) {
            parentMap.put(stack.pop(), v);
        }
        return v;
    }

    public void union(V a, V b) {
        V aHead = findHead(a);
        V bHead = findHead(b);
        if (aHead != bHead) {
            int aSize = sizeMap.get(aHead);
            int bSize = sizeMap.get(bHead);
            V larger = aSize >= bSize ? aHead : bHead;
            V smaller = larger == aHead ? bHead : aHead;
            parentMap.put(smaller, larger);
            sizeMap.put(larger, aSize + bSize);
            sizeMap.remove(smaller);
        }
    }

    public boolean isSameSet(V a, V b) {
        return findHead(a) == findHead(b);
    }
    
    public int sets() {
        return sizeMap.size();
    }
}