Skip to content

2316. Count Unreachable Pairs of Nodes in an Undirected Graph

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1:

img

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

Example 2:

img

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[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]].
Therefore, we return 14.

Constraints:

  • 1 <= n <= 105
  • 0 <= edges.length <= 2 * 105
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no repeated edges.

Solution:

class Solution {
    public long countPairs(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int i = 0; i < n; i++){
            graph.put(i, new ArrayList<>());
        }

        for (int[] edge : edges){
            int from = edge[0];
            int to = edge[1];
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
        // 0: 1, 2, 3, 4

        Set<Integer> visited = new HashSet<>();
        List<Integer> s = new ArrayList<>();

        for (int i = 0; i < n; i++){
            if (!visited.contains(i)){
                int cur = dfs(i, visited, graph);
                s.add(cur);
            }
        }
        // int result = 0;

        // for (int i = 0; i < s.size() - 1; i++){
        //     int cur = s.get(i);
        //     for (int j = i + 1; j < s.size(); j++){
        //         int next = s.get(j);
        //         result = result + cur * next;
        //     }
        // }

        long totalPairs = (long) n * (n - 1) / 2;
        long reachablePairs = 0;

        for (int size : s){
            reachablePairs += (long) size * (size - 1) /2;
        }
      // 强制转换size 为long之前进行乘法运算.

        return totalPairs - reachablePairs;

    }

    private int dfs(int i, Set<Integer> visited, Map<Integer, List<Integer>> graph){
        if (visited.contains(i)){
            return 0;
        }

        visited.add(i);// 0
        int count = 1; // 0
        List<Integer> nei = graph.get(i);
        for (int next : nei){
            if (!visited.contains(next)){
                count = count + dfs(next, visited, graph);
            }
        }

        return count;

    }
}

/*
    7 - 3 = 4


    4 

    4*1 + 4 * 2 + 1* 2 = 4 + 8 + 2 = 14



*/