# 使用并查集处理集合的合并和查询问题

## 要解决的问题

``````boolean isSameSet(V x,V y);
``````

``````void union(V x, V y)
``````

## 数据结构设计

``````        private static class Node<V> {
private final V value;

public Node(V value) {
this.value = value;
}
}
``````

``````// 快速找到某个节点是否存在
private HashMap<V, Node<V>> nodeMap;
// 找到某个节点的父节点
private HashMap<Node<V>, Node<V>> parentMap;
// 每个代表节点代表的节点个数
private HashMap<Node<V>, Integer> sizeMap;
``````

``````parentMap.get(x)
``````

``````union(a,b)
``````

``````union(b,d)
``````

``````union(b,h)
``````

``````union(e,g)
union(g,j)
``````

``````union(j,b)
``````

## 并查集的优化

``````union(b,d)
``````

``````        private Node<V> findFather(Node<V> node) {
// 沿途节点都放队列里面
// 然后将队列元素做扁平化操作
while (node != parentMap.get(node)) {
queue.offer(node);
node = parentMap.get(node);
}
while (!queue.isEmpty()) {
// 优化2：扁平化操作
parentMap.put(queue.poll(), node);
}
return node;
}
``````

## 完整代码

``````package snippet;

import java.util.HashMap;
import java.util.List;
import java.util.Queue;

public class Code_0049_UnionFind {

public static class UnionFind<V> {
// 快速找到某个节点是否存在
private HashMap<V, Node<V>> nodeMap;
// 找到某个节点的父节点
private HashMap<Node<V>, Node<V>> parentMap;
// 每个代表节点代表的节点个数
private HashMap<Node<V>, Integer> sizeMap;

public UnionFind(List<V> values) {
nodeMap = new HashMap<>();
parentMap = new HashMap<>();
sizeMap = new HashMap<>();
for (V v : values) {
Node<V> n = new Node<>(v);
nodeMap.put(v, n);
parentMap.put(n, n);
sizeMap.put(n, 1);
}
}

// v1，v2必须是已经存在nodeMap中的元素
public void union(V v1, V v2) {
if (!nodeMap.containsKey(v1) || !nodeMap.containsKey(v2)) {
return;
}
if (!isSameSet(v1, v2)) {
Node<V> v1Parent = nodeMap.get(v1);
Node<V> v2Parent = nodeMap.get(v2);
Node<V> small = sizeMap.get(v1Parent) > sizeMap.get(v2Parent) ? v2Parent : v1Parent;
Node<V> large = small == v1Parent ? v2Parent : v1Parent;
sizeMap.put(large, sizeMap.get(large) + sizeMap.get(small));
// 优化1：小集合挂在大集合下面
parentMap.put(small, large);
parentMap.remove(small);
}
}

private Node<V> findFather(Node<V> node) {
while (node != parentMap.get(node)) {
queue.offer(node);
node = parentMap.get(node);
}
while (!queue.isEmpty()) {
// 优化2：扁平化操作
parentMap.put(queue.poll(), node);
}
return node;
}

public boolean isSameSet(V v1, V v2) {
if (!nodeMap.containsKey(v1) || !nodeMap.containsKey(v2)) {
return false;
}
return findFather(nodeMap.get(v1)) == findFather(nodeMap.get(v2));
}

private static class Node<V> {
private final V value;

public Node(V value) {
this.value = value;
}
}
}
}
``````

## 参考资料

原文作者：Grey Zeng
原文地址: https://www.cnblogs.com/greyzeng/p/16340125.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。