并查集

1. 定义

维基百科：并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：

• 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
• 合并：将两个集合合并为一个。
• 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

2. 并查集代码

static class UF{
        private int[] parent;
        private int count;
        public UF(int n) {
            parent = new int[n];
            for(int i = 0;i < n;i++) {
                parent[i] = i;
            }
            this.count = n;
        }
        public int find(int x) {
            while(parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        public boolean isConnect(int x,int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            return xRoot == yRoot;
        }
        public void union(int x,int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            parent[x] = yRoot;
            count--;
        }
        public int getCount(){
            return count;
        }
    }

2.1 代码解读

并查集代码使用一个数组模拟节点集合组成的森林，parent[x]的值代表节点x的父亲节点为parent[x]，count代表连通分量的数量。主要操作有find和union，作用分别是查询某个节点的根节点和连通两个节点。find函数中使用了路径压缩来优化，使得并查集的合并操作和查询操作都可以做到常数级别的时间复杂度。

题目

你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。

返回 图中已连接分量的数目 。

示例 1:

输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2
示例 2:

输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出: 1

public class Leetcode323 {
    public int countComponents(int n, int[][] edges) {
        UF uf = new UF(n);
        for(int[] edge:edges) {
            if(!uf.isConnect(edge[0],edge[1])) {
                uf.union(edge[0],edge[1]);
            }
        }
        return uf.getCount();
    }
    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{3,4}};
        Leetcode323 leetcode323 = new Leetcode323();
        System.out.println(leetcode323.countComponents(5,edges));
    }
    static class UF{
        private int[] parent;
        private int count;
        public UF(int n) {
            parent = new int[n];
            for(int i = 0;i < n;i++) {
                parent[i] = i;
            }
            this.count = n;
        }
        public int find(int x) {
            while(parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        public boolean isConnect(int x,int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            return xRoot == yRoot;
        }
        public void union(int x,int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            parent[x] = yRoot;
            count--;
        }
        public int getCount(){
            return count;
        }
    }
}