认识并查集结构

package com.algorithm.practice;

import javafx.scene.Parent;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

class  Node{

}

public  class UnionFindSet {
    HashMap<Node,Node> fatherMap; //存结点和该结点的父节点
    HashMap<Node,Integer> sizeMap;//存结点和结点的后挂结点数量

    public UnionFindSet(List<Node> nodes){
          makeSets(nodes);
    }

    private void makeSets(List<Node> nodes) { //将每个结点
        fatherMap=new HashMap<>();
        sizeMap=new HashMap<>();
        for (Node node: nodes
             ) {
            fatherMap.put(node,node);
            sizeMap.put(node,1);
        }
    }
    public Node findRootFather(Node node){
        Stack<Node> stack=new Stack<>();
        Node cur=node;
        Node father = fatherMap.get(node);
        while (father!=cur){
            stack.push(cur);
            cur=father;
            father=fatherMap.get(cur);
        }

        while (!stack.isEmpty())
        {
            fatherMap.put(stack.pop(),father);
        }
        return father;
    }
    public boolean isSameSet(Node node1,Node node2){
        return findRootFather(node1)==findRootFather(node2);
    }

    public void  union(Node a,Node b){
        if (a==null||b==null){
            return;
        }
        Node ahead=findRootFather(a);
        Node bhead=findRootFather(b);
        if (ahead!=bhead){ //两者的根节点不一样才合并
            int aHeadSize=sizeMap.get(ahead);
            int bHeadSize=sizeMap.get(bhead);
            if (aHeadSize<=bHeadSize){
                //如果a的头下长度比b头下长度小,a合并到b链下
                fatherMap.put(ahead,bhead);
                sizeMap.put(bhead,bHeadSize+aHeadSize);
            }else
            {
                fatherMap.put(bhead,ahead);
                sizeMap.put(ahead,bHeadSize+aHeadSize);
            }

        }


    }



}