并查集.md

并查集

并查集的实现，并查集主要实现两个功能，合并两个集合，判断两个节点（自己建出来的）是否在同一集合

    public static class UnionSet<V>{
    
        //没一个数值分别对应一个节点
        public HashMap<V,Node<V>> nodes;
        //每一个节点直接的父节点
        public HashMap<Node<V>,Node<V>> parents;
        //每一个集合的头节点，并且集合所含的节点数
        public HashMap<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 static class Node<V>{
        V value;
        public Node(V v){
            value=v;
        }
    }
        public Node<V> findFather(Node<V> cur){
            //申请一个栈，把沿途的节点数全压栈
            Stack<Node<V>> path=new Stack<>();
            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){
            //如果nodes不包含a,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){
                int aSetSize=sizeMap.get(aHead);//找出最大的集合
                int bSetSize=sizeMap.get(bHead);
                Node<V> big=aSetSize>=bSetSize?aHead:bHead;
                Node<V> small=big==aHead?bHead:aHead;
                parents.put(small,big);//小集合的爹改成大集合的顶层节点
                sizeMap.put(big,aSetSize+bSetSize);//更新sizeMap
                sizeMap.remove(small);
            }
        }
    }

身份问题

一个人的身份有三个特征，只要有一个特征相同，那么为同一个人，返回最大有几个人

    public static class User{
        public String a;
        public String b;
        public String c;
        public User(String a,String b,String c){
            this.a=a;
            this.b=b;
            this.c=c;
        }
    }
    public static int mergeUsers(List<User> users){
        UnionSet<User> unionFind=new UnionSet<>(users);
        //三个哈希表分别存储三个特征
        HashMap<String,User> mapA=new HashMap<>();
        HashMap<String,User> mapB=new HashMap<>();
        HashMap<String,User> mapC=new HashMap<>();
        for(User user:users){
        //对于每一个user，分别进三个哈希表，没有就加进去，有就合并
            if(mapA.containsKey(user.a)){
                unionFind.union(user,mapA.get(user.a));
            } else{
                mapA.put(user.a,user);
            }
            if(mapB.containsKey(user.b)){
                unionFind.union(user,mapB.get(user.b));
            } else{
                mapB.put(user.b,user);
            }
            if(mapC.containsKey(user.c)){
                unionFind.union(user,mapC.get(user.c));
            } else{
                mapC.put(user.c,user);
            }
        }
        return unionFind.getSetNum();
        
    }