基本概念

• 并查集是一种数据结构
• 并查集这三个字，一个字代表一个意思。
  • 并（Union），代表合并
  • 查（Find），代表查找
  • 集（Set），代表这是一个以字典为基础的数据结构，它的基本功能是合并集合中的元素，查找集合中的元素
• 并查集的典型应用是有关连通分量的问题
• 并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)。 因此，并查集可以应用到在线算法中。

数据结构

• 并查集跟树有些类似，只不过她跟树是相反的。在树这个数据结构里面，每个节点会记录它的子节点。在并查集里，每个节点会记录它的父节点。

完整模板

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);
        }
    }
    //将A,B（不共根节点的两节点）插入到一个集合中
    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY){
            father.put(rootX,rootY);
        }
    }
    
    public int find(int x) {
    	//寻找根节点
        int root = x;
        
        while(father.get(root) != null){
            root = father.get(root);
        }
        //路径压缩，防止并查集退化成链表
        while(x != root){
            int original_father = father.get(x);
            father.put(x,root);
            x = original_father;
        }
        
        return root;
    }
    //判断x, y 的是否相连（根节点是否相同）
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
} 

例题：lc547.省份数量

class UnionFind{
    // 记录父节点
    private Map<Integer, Integer> father;
    // 记录集合的数量
    private int numOfSets = 0;

    public UnionFind() {
        father = new HashMap<Integer, Integer>();   
        numOfSets = 0;
    }
    
    public void add(int x) {
        if (!father.containsKey(x)) {
            father.put(x, null);
            numOfSets++;
        }
    }

    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            father.put(rootX, rootY);
            numOfSets--;
        }
    }

    public int find(int x) {
        int root = x;
        while (father.get(root) != null) {
            root = father.get(root);
        }
        while (x != root) {
            int original_father = father.get(x);
            father.put(x, root);
            x = original_father;
        }
        return root;
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    public int getNumOfSets(){
        return numOfSets;
    }
}

class Solution {
    
    public int findCircleNum(int[][] isConnected) {
        UnionFind uf = new UnionFind();
        for (int i = 0; i < isConnected.length; i++) {
            uf.add(i);
            for (int j = 0; j < i; j++) {
                if (isConnected[i][j] == 1) {
                    uf.merge(i, j);
                }
            }
        }
        return uf.getNumOfSets();
    }
}