//并查集大致框架---代碼中的數(shù)據(jù)（Node），可以是其他，比如二叉樹(shù)節(jié)點(diǎn)、圖的邊、節(jié)點(diǎn)等等 抽象的數(shù)據(jù)
public class UnionSet {
    private HashMap<Node, Node> fatherMap; //key表示當(dāng)前這個(gè)數(shù)據(jù)，value表示這個(gè)數(shù)據(jù)的代表（父親）是誰(shuí)
    private HashMap<Node, Integer> sizeMap; //表示當(dāng)前這個(gè)組（集合）的大小
    
    public UnionSet() { //構(gòu)造方法
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
    }
    
    public void makeSet(List<Node> list) { //生成初始化狀態(tài)的并查集，剛開(kāi)始每個(gè)數(shù)據(jù)都是獨(dú)立的
        
    }
    
    public boolean isSameSet(Node node1, Node node2) { //判斷當(dāng)前這兩個(gè)數(shù)據(jù)，是不是一個(gè)組的？
        
    }
    
    private Node findFather(Node node) { //查找這個(gè)數(shù)據(jù)，它那個(gè)組的代表（父親）是誰(shuí)？
        
    }
    
    public void union(Node node1, Node node2) { //將這兩個(gè)數(shù)據(jù)，放到一個(gè)組
         
    }
}

//初始化并查集
public void makeSet(List<Node> list) {
    if (list == null) {
        return;
    }
    fatherMap.clear();
    sizeMap.clear(); //先將表清空
    
    //遍歷list，把每一個(gè)節(jié)點(diǎn)，都放入哈希表中
    for (Node node : list) {
        fatherMap.put(node, node); //第一個(gè)參數(shù)是節(jié)點(diǎn)本身，第二個(gè)參數(shù)就是這個(gè)組的代表
        sizeMap.put(node, 1); //第一個(gè)參數(shù)是這個(gè)組的代表，第二個(gè)參數(shù)是大小
    }
}

//判斷是不是同一個(gè)組
public boolean isSameSet(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return false;
    }
    return findFather(node1) == findFather(node2); //查找各自的代表節(jié)點(diǎn)，看是不是同一個(gè)。
}

//查找代表節(jié)點(diǎn)，并做路徑壓縮
private Node findFather(Node node) {
    if (node == null) {
        return null;
    }
    //查找代表節(jié)點(diǎn)
    Stack<Node> path = new Stack<>(); //存儲(chǔ)沿途的節(jié)點(diǎn)
    while (node != fatherMap.get(node)) { //代表節(jié)點(diǎn)不是自己本身，就繼續(xù)查找
        path.push(node);
        node = fatherMap.get(node);
    }
    //路徑壓縮
    while (!path.isEmpty()) {
        Node tmp = path.pop();
        fatherMap.put(tmp, node); //此時(shí)的node，就是這個(gè)組的代表節(jié)點(diǎn)
    }
    
    return node;
}

//合并操作
public void union(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    int node1Size = sizeMap.get(node1);
    int node2Size = sizeMap.get(node2); //分別得到兩個(gè)節(jié)點(diǎn)所在組的大小
    Node node1Father = fatherMap.get(node1);
    Node node2Father = fatherMap.get(node2); //分別拿到兩個(gè)節(jié)點(diǎn)的代表節(jié)點(diǎn)
    
    if (node1Father != node2Father) { //兩個(gè)節(jié)點(diǎn)，不在同一個(gè)組，就合并
        if (node1Size < node2Size) { //node1 掛在 node2
            fatherMap.put(node1Father, node2Father);
            sizeMap.put(node2Father, node1Size + node2Size); //新的組，大小是原來(lái)兩個(gè)組的和
            sizeMap.remove(node1Father); //小組的數(shù)據(jù)，就不需要了，刪除
        } else { //node2 掛在 node1
            //跟上面操作類似
            fatherMap.put(node2Father, node1Father); 
            sizeMap.put(node1Father, node1Size + node2Size);
            sizeMap.remove(node1Father);
        }
    }
}