import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Unioned {//并查集
public static class Element<V> {//先将数据"圈"起来
public V value;
public Element(V value) { this.value = value; }
}
public static class UnionFindSet<V> {
public HashMap<V, Element<V>> elementMap; //存储字符指向的节点
public HashMap<Element<V>, Element<V>>
fatherMap; //两两一组,存储当前节点与父节点信息
public HashMap<Element<V>, Integer> rankMap; //代表"头节点"所拥有的点集大小
public UnionFindSet(List<V> list) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
rankMap = new HashMap<>();
for (V v : list) {
Element<V> element = new Element<V>(v);
elementMap.put(v, element);
fatherMap.put(element, element);
rankMap.put(element, 1);
}
}
public Element<V> findHead(Element<V> element) {//寻找头节点
Stack<Element<V>> path = new Stack<>();
while (element != fatherMap.get(element)) {//如果当前节点并不是最顶上的节点
path.push(element);
element = fatherMap.get(element);
}
while (!path.isEmpty()) {
fatherMap.put(path.pop(), element);
}
return element;
}
public boolean isSameSet(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
return false;
}
public void union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
Element<V> aF = findHead(elementMap.get(a));
Element<V> bF = findHead(elementMap.get(b));
if (aF != bF) {
Element<V> big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF;
Element<V> small = big == aF ? bF : aF;
fatherMap.put(small, big);
rankMap.put(big, rankMap.get(aF) + rankMap.get(bF));
rankMap.remove(small);
}
}
}
}
}
文章评论