并查集

应用范围：

一开始我有n个集合，这个集合可以先理解为数学上的集合，每个节点都首先自成一个集合，n个节点就相当于有n个集合。并查集支持的操作：你想查两个节点是否来自同一个集合，或者想合并两个集合

前提：

每个节点必须先自成一个集合，所有点必须建立一个集合

优点：

如果你有n个节点，你想查两个节点是否来自于一个集合的操作数（操作发生的次数），例如你想查两个节点是否来自于一个集合的操作次数是k，集合合并的次数为f，并且k（次数）+f（次数）是O（n），并查集的操作次数是O（n），平均查询和合并的时间复杂度为O（1）

递归过程解析

image.png

代码：

public static class Node {
        // whatever you like
    }

    public static class DisjointSets {
        public HashMap<Node, Node> fatherMap;
        public HashMap<Node, Integer> rankMap;

        public DisjointSets() {
            fatherMap = new HashMap<Node, Node>();
            rankMap = new HashMap<Node, Integer>();
        }

        public void makeSets(List<Node> nodes) {
            fatherMap.clear();
            rankMap.clear();
            for (Node node : nodes) {
                fatherMap.put(node, node);
                rankMap.put(node, 1);
            }
        }

        public Node findFather(Node n) {
            Node father = fatherMap.get(n);
            if (father != n) {
                father = findFather(father);
            }
            fatherMap.put(n, father);
            return father;
        }

        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aFather = findFather(a);
            Node bFather = findFather(b);
            if (aFather != bFather) {
                int aFrank = rankMap.get(aFather);
                int bFrank = rankMap.get(bFather);
                if (aFrank <= bFrank) {
                    fatherMap.put(aFather, bFather);
                    rankMap.put(bFather, aFrank + bFrank);
                } else {
                    fatherMap.put(bFather, aFather);
                    rankMap.put(aFather, aFrank + bFrank);
                }
            }
        }

    }