我要评论
public class UnionSet<V> {
public static class Node<V>{
V value;
public Node(V value) {
this.value = value;
}
}
public Map<V, Node<V>> nodes;
public Map<Node<V>, Node<V>> parents;
public Map<Node<V>, Integer> sizeMap;
public UnionSet(List<V> values) {
for (V value : values) {
Node<V> node = new Node<>(value);
nodes.put(value, node);
parents.put(node, node);
sizeMap.put(node, 1);
}
}
public Node<V> findFather(Node<V> cur) {
Deque<Node<V>> path = new LinkedList<>();
while (cur != parents.get(cur)) {
path.push(cur);
cur = parents.get(cur);
}
while (!path.isEmpty()) {
parents.put(path.pop(), cur);
}
return cur;
}
public boolean isSameSet(V a, V b) {
if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
return false;
}
return findFather(nodes.get(a)) == findFather(nodes.get(b));
}
public void union(V a, V b) {
if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
return;
}
Node<V> aHead = findFather(nodes.get(a));
Node<V> bHead = findFather(nodes.get(b));
if (aHead != bHead) {
Integer aSetSize = sizeMap.get(aHead);
Integer bSetSize = sizeMap.get(bHead);
if (aSetSize >= bSetSize) {
parents.put(bHead, aHead);
sizeMap.put(aHead, aSetSize + bSetSize);
sizeMap.remove(bHead);
} else {
parents.put(aHead, bHead);
sizeMap.put(bHead, aSetSize + bSetSize);
sizeMap.remove(aHead);
}
}
}
public int getSetNum() {
return sizeMap.size();
}
}
本文地址：https://blog.csdn.net/ZhaoXia_hit/article/details/107679698
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论