2316. 统计无向图中无法互相到达点对数 (opens new window)

1.深搜+连通分量

思路：如果需要彻底遍历判断每两个节点是否联通，则时间复杂度比较高。弗洛伊德算法n*3

实际上，我们只需要计算出每个连通分量的大小，联通分量内任意两个节点之间肯定是连通的。

假设当前连通分量的大小为k，那么当前连通分量的无法到达点对数为k*(n-k)。

class Solution {
    Map<Integer,Set<Integer>> map=new HashMap<>();
    public long countPairs(int n, int[][] edges) {
        long res=0;
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            if(!map.containsKey(x)) map.put(x, new HashSet<>());
            if(!map.containsKey(y)) map.put(y, new HashSet<>());
            Set<Integer> set1 = map.get(x);
            Set<Integer> set2 = map.get(y);
            set1.add(y);
            set2.add(x);
        }
        Set<Integer> set=new HashSet<>();
        Set<Integer> visit=new HashSet<>();
        for(int i=0;i<n;i++){
            if(!set.contains(i)){
                visit.clear();
                visit.add(i);
                find(i,visit);
                int a=n-set.size()-visit.size();
                res+=1l*a*visit.size();
                set.addAll(visit);
            }
        }
        return res;
    }
    public void find(int start,Set<Integer> visit){
        if(map.containsKey(start)){
            Set<Integer> currSet=map.get(start);
            for (Integer next : currSet) {
                if (!visit.contains(next)) {
                    visit.add(next);
                    find(next, visit);
                }
            }
        }
    }
}