【算法】lc323 无向图中连通分量的数目

原题链接
题目大意

323. 无向图中连通分量的数目
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

示例 1:

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

     0          3
     |          |
     1 --- 2    4 

输出: 2
示例 2:

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

     0           4
     |           |
     1 --- 2 --- 3

输出:  1
注意:
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0]  相同，所以它们不会同时在 edges 中出现。

思路：利用利用并查集 + hashset去重统计大小

class Solution {
    int[] p;
    int[] size;
    public int countComponents(int n, int[][] edges) {
        p = new int[n];
        for(int i = 0; i < n; i ++){//构建祖宗集合
            p[i] = i;
        }
        for(int[] a : edges){
            union(a[0],a[1]);
        }
        Set<Integer> set = new HashSet<>();
        for(int x : p){
            set.add(find(x));//去重，祖宗的孩子可能有很多
        }
        return set.size();//有多少个祖宗就有多少个连通分量
    }
    public void union(int a,int b){//构建p
        if(find(a) == find(b))return;
        p[find(a)] = find(b);

    }
    public int find(int x){//返回祖宗节点 +  路径压缩
        if(x != p[x])p[x] = find(p[x]);
        return p[x];
    }
}