统计无向图中无法互相到达点对数

问题：

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。

示例：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。

输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

思路：

需要一个布尔类型数组记录每个节点是否被访问过，还需要map记录每个节点相邻的其他节点。通过深度优先遍历统计每个联通图的节点数。根据二项式法则，求出结果。

代码：

class Solution {
    public long countPairs(int n, int[][] edges) {
        long ans = 0;
        int len = edges.length;
        //极端情况一条边都没有,符合CN2
        if(len == 0){
            return ((long)n * (long)(n-1)) / 2;
        }
        //记录点与点之间的互通情况
        HashMap> map = new HashMap<>();
        //标志位
        boolean[] flag = new boolean[n];
        //每个联通图节点数
        int[] points = new int[n];
 
        for(int[] val : edges){
            addEdges(val[0],val[1],map);
            addEdges(val[1],val[0],map);
        }
        for(int i = 0;i < n; i++){
            if(flag[i] == false){
                dfs(i,i,flag,points,map);
            }
        }
        Arrays.sort(points);
        for(int i = 0; i < n; i++){
            if(points[i] == 0){
                continue;
            }
            for(int j = i+1; j < n; j++){
                ans += (long)points[i]*(long)points[j];
            }
        }
        return ans;
    }
 
    public void dfs(int start, int point, boolean[] flag, int[] points,  HashMap> map) {
        ArrayList list = map.get(point);
        flag[point] = true;
        points[start]++;
        if(list != null){
            for(int next: list){
                if(flag[next]==false){
                    dfs(start,next,flag,points,map);
                }
            }
        }
       
    }
    public void addEdges(int start, int point, HashMap> map){
        ArrayList list = map.get(start);
        if(list == null){
            list = new ArrayList<>();
        }
        list.add(point);
        map.put(start,list);
    }
}