并查集最佳实践

约定不等于承诺〃 2022-09-04 13:58 190阅读 0赞

### 并查集 ###

欢迎关注我的公众号 [dying 搁浅][dying] 希望本文对你有所帮助

show the code 几乎所有连通问题，合并问题都可以考虑使用并查集进行优雅求解

/** * @program: dying-stranded * @description: 并查集 * 标准并查集提供两个方法，这两个方法时间复杂度为 O(1) * 合并（union）：把两个不相交的集合合并为一个集合。 * 查询是否为同一集合（isSameSet）：查询两个元素是否在同一个集合中。 * @author: wangzibin **/

package com.dying.stranded.algorithm.base;
    import com.google.common.base.Objects;
    import com.google.common.collect.Maps;
    import org.apache.commons.collections4.CollectionUtils;
    
    import java.util.*;
    
    /** * @program: dying-stranded * @description: 并查集 * 标准并查集提供两个方法，这两个方法时间复杂度为 O(1) * 合并（union）：把两个不相交的集合合并为一个集合。 * 查询是否为同一集合（isSameSet）：查询两个元素是否在同一个集合中。 * @author: wangzibin **/
    public class UnionFindSet<T> { 
    
        static class Node<T> { 
    
            T value;
    
            Node(T t) { 
                value = t;
            }
    
            @Override
            public boolean equals(Object o) { 
                return this == o;
            }
    
            @Override
            public int hashCode() { 
                return Objects.hashCode(value);
            }
        }
    
        /** * 记录所有节点 */
        Map<T, Node<T>> nodes;
        /** * 记录所有节点父节点 */
        Map<Node<T>, Node<T>> parents;
        /** * 记录代表节点集合大小 */
        Map<Node<T>, Integer> setSize;
    
        public UnionFindSet(Collection<T> collection) { 
            if (CollectionUtils.isEmpty(collection)) { 
                return;
            }
            nodes = Maps.newHashMap();
            parents = Maps.newHashMap();
            setSize = Maps.newHashMap();
            for (T item : collection) { 
                Node<T> node = new Node<>(item);
                nodes.put(item, node);
                parents.put(node, node);
                setSize.put(node, 1);
            }
        }
    
        public void union(T t1, T t2) { 
            Node<T> t1RootNode = findRootNode(t1);
            Node<T> t2RootNode = findRootNode(t2);
            if (t1RootNode == null || t2RootNode == null) { 
                return;
            }
            if (isSameNode(t1RootNode, t2RootNode)) { 
                return;
            }
            Integer t1SetSize = setSize.get(t1RootNode);
            Integer t2SetSize = setSize.get(t2RootNode);
            // 小集合挂大集合 优化找 root 节点速度
            Node<T> parentNode = t1SetSize > t2SetSize ? t1RootNode : t2RootNode;
            Node<T> subNode = t1SetSize > t2SetSize ? t2RootNode : t1RootNode;
            parents.put(subNode, parentNode);
            setSize.put(parentNode, t1SetSize + t1SetSize);
            setSize.remove(subNode);
    
        }
    
        public boolean isSameSet(T t1, T t2) { 
            Node<T> t1RootNode = findRootNode(t1);
            Node<T> t2RootNode = findRootNode(t2);
            return isSameNode(t1RootNode, t2RootNode);
        }
    
        public Integer getSetSize() { 
            return setSize.size();
        }
    
        private boolean isSameNode(Node<T> node1, Node<T> node2) { 
            if (node1 == null || node2 == null) { 
                return false;
            }
            return node1.equals(node2);
        }
    
        /** * @Description: 寻找代表节点 * @Param item * @Return: com.dying.stranded.algorithm.base.UnionFindSet.Node<T> * @Author: wangzibin */
        private Node<T> findRootNode(T item) { 
    
            Node<T> current = nodes.get(item);
            if (current == null) { 
                return null;
            }
            Stack<Node<T>> path = new Stack<>();
            while (current != parents.get(current)) { 
                path.push(current);
                current = parents.get(current);
            }
            // 这里做优化将查询路径上的所有节点直接指向根，将链扁平化，优化后续查询速度
            while (!path.isEmpty()) { 
                parents.put(path.pop(), current);
            }
            return current;
        }
    
    }

### Leecode 例题 [547. 省份数量][547.] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3c5MDMzMjg2MTU_size_16_color_FFFFFF_t_70]

直接给出 AC 代码：

import java.util.*;
    
    /** * @program: dying-stranded * @description: * @author: wangzibin **/
    public class Solution { 
    
        public static int findCircleNum(int[][] isConnected) { 
            List<Integer> items = new ArrayList<>();
            for (int i = 0; i < isConnected.length; i++) { 
                items.add(i);
            }
            UnionFindSet<Integer> unionFindSet = new UnionFindSet<>(items);
            for (int i = 0; i < isConnected.length; i++) { 
                for (int j = 0; j < isConnected[i].length; j++) { 
                    if (isConnected[i][j] == 1) { 
                        unionFindSet.union(i, j);
                    }
                }
            }
            return unionFindSet.getSetSize();
        }
    
    
        static class UnionFindSet<T> { 
    
            static class Node<T> { 
    
                T value;
    
                Node(T t) { 
                    value = t;
                }
    
                @Override
                public boolean equals(Object o) { 
                    return this == o;
                }
    
                @Override
                public int hashCode() { 
                    return Objects.hashCode(value);
                }
            }
    
            /** * 记录所有节点 */
            Map<T, Node<T>> nodes;
            /** * 记录所有节点父节点 */
            Map<Node<T>, Node<T>> parents;
            /** * 记录代表节点集合大小 */
            Map<Node<T>, Integer> setSize;
    
            public UnionFindSet(Collection<T> collection) { 
                if (collection==null||collection.isEmpty()) { 
                    return;
                }
                nodes = new HashMap<>();
                parents = new HashMap<>();
                setSize = new HashMap<>();
                for (T item : collection) { 
                    Node<T> node = new Node<>(item);
                    nodes.put(item, node);
                    parents.put(node, node);
                    setSize.put(node, 1);
                }
            }
    
            public void union(T t1, T t2) { 
                Node<T> t1RootNode = findRootNode(t1);
                Node<T> t2RootNode = findRootNode(t2);
                if (t1RootNode == null || t2RootNode == null) { 
                    return;
                }
                if (isSameNode(t1RootNode, t2RootNode)) { 
                    return;
                }
                Integer t1SetSize = setSize.get(t1RootNode);
                Integer t2SetSize = setSize.get(t2RootNode);
                // 小集合挂大集合 优化找 root 节点速度
                Node<T> parentNode = t1SetSize > t2SetSize ? t1RootNode : t2RootNode;
                Node<T> subNode = t1SetSize > t2SetSize ? t2RootNode : t1RootNode;
                parents.put(subNode, parentNode);
                setSize.put(parentNode, t1SetSize + t1SetSize);
                setSize.remove(subNode);
    
            }
    
            public boolean isSameSet(T t1, T t2) { 
                Node<T> t1RootNode = findRootNode(t1);
                Node<T> t2RootNode = findRootNode(t2);
                return isSameNode(t1RootNode, t2RootNode);
            }
    
            public Integer getSetSize() { 
                return setSize.size();
            }
    
            private boolean isSameNode(Node<T> node1, Node<T> node2) { 
                if (node1 == null || node2 == null) { 
                    return false;
                }
                return node1.equals(node2);
            }
    
            /** * @Description: 寻找代表节点 * @Param item * @Return: Node<T> * @Author: wangzibin */
            private Node<T> findRootNode(T item) { 
    
                Node<T> current = nodes.get(item);
                if (current == null) { 
                    return null;
                }
                Stack<Node<T>> path = new Stack<>();
                while (current != parents.get(current)) { 
                    path.push(current);
                    current = parents.get(current);
                }
                // 这里做优化将查询路径上的所有节点直接指向根，将链扁平化，优化后续查询速度
                while (!path.isEmpty()) { 
                    parents.put(path.pop(), current);
                }
                return current;
            }
        }
    }

最后分享一个很有意思的网站： [深海][Link 1]

[dying]: https://mp.weixin.qq.com/s/9n-F1jPMfmOK6uW_LXqOHQ
[547.]: https://leetcode-cn.com/problems/number-of-provinces/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3c5MDMzMjg2MTU_size_16_color_FFFFFF_t_70]: /images/20220829/1ab414cdca1d46309ad75982a4d0263e.png
[Link 1]: https://neal.fun/deep-sea/