并查集练习

package com.harrison.class10;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code02_MergeUsers {
  public static class Node<V>{
    V value;
    public Node(V v) {
      value=v;
    }
  }
  public static class UnionSet<V>{
    HashMap<V, Node<V>> nodes;
    HashMap<Node<V>, Node<V>> parents;
    HashMap<Node<V>, Integer> sizeMap;
    public UnionSet(List<V> values) {
      for(V cur:values) {
        Node<V> node=new Node<>(cur);
        nodes.put(cur, node);
        parents.put(node, node);
        sizeMap.put(node, 1);
      }
    }
    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) {
      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.remove(small);
      }
    }
    public int getSizeNum() {
      return sizeMap.size();
    }
  }
  public static class Users {
    public String a;
    public String b;
    public String c;
    public Users(String a, String b, String c) {
      this.a = a;
      this.b = b;
      this.c = c;
    }
  }
  // 如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人
  // 请合并users，返回合并之后的用户数量
  public static int mergeUsers(List<Users> users) {
    UnionSet<Users> unionSet=new UnionSet<>(users);
    // a字段的map, key:a字段的值  value:拥有a字段的User
    HashMap<String, Users> mapA=new HashMap<>();
    HashMap<String, Users> mapB=new HashMap<>();
    HashMap<String, Users> mapC=new HashMap<>();
    for(Users cur:users) {
      // 如果当前用户拥有a字段
      // 那么就将当前用户所在的集合 和 之前拥有a字段的用户所在的集合 进行合并
      // b,c字段都这样做
      if(mapA.containsKey(cur.a)) {
        unionSet.Union(cur, mapA.get(cur.a));
      }else {// 否则就是一个新字段
        mapA.put(cur.a, cur);
      }
      if(mapB.containsKey(cur.b)) {
        unionSet.Union(cur, mapB.get(cur.b));
      }else {
        mapB.put(cur.b, cur);
      }
      if(mapC.containsKey(cur.c)) {
        unionSet.Union(cur, mapC.get(cur.c));
      }else {
        mapC.put(cur.c, cur);
      }
    }
    // 向并查集询问合并之后还剩多少个集合
    return unionSet.getSizeNum();
  }
}