LeetCode数据结构篇

并查集

并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

基础写法：（自己试一下，要能够独立写出）

import java.util.HashMap;
import java.util.Map;

public class UnionFind {
    private Map<Integer, Integer> father; //用于记录父节点

    //构造器
    public UnionFind() {
        father = new HashMap<Integer, Integer>();// 初始化父节点
    }

    //首先要根据图中的节点初始化并查集
    public void add(int x){
        if(!father.containsKey(x)){
            father.put(x, null); //父节点为空
        }
    }
    
    //并查集中的并操作
    public void merge(int x, int y){
        int fx = find(x); //找到x的父节点
        int fy = find(y); //找到y的父节点
        if(fx!= fy){ //如果x和y的父节点不同，则将y的父节点设为x的父节点
            father.put(fy, fx);
        }
    }

    //并查集中的查找操作
    public int find(int x){
        int root = x; //初始化根节点为x
        while(father.get(root)!= null){ //如果父节点不为空，则一直向上找
            root = father.get(root); //更新根节点
        }
        return root; //返回根节点
    }
    
    //判断两个节点是否属于同一个集合
    public boolean isConnected(int x, int y){
        return find(x) == find(y); //如果x和y的根节点相同，则属于同一个集合
    }
}