2316.Count Unreachable Pairs of Nodes in an Undirected Graph

tags: Medium,DFS,BFS,Graph

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] = [

$a_i$,

$b_i$] denotes that there exists an undirected edge connecting nodes

$a_i$ and

$b_i$.

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

範例

Example 1:

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:

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 <= 10⁵
• 0 <= edges.length <= 2 * 10⁵
• edges[i].length == 2
• 0 <=
  $a_i$,
  $b_i$ < n
• $a_i$ !=
  $b_i$
• There are no repeated edges.

解答

Python

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        visits = set()
        def dfs(node):
            visits.add(node)
            count = 1
            for child in graph[node]:
                if child in visits: continue
                count += dfs(child)
            return count
        
        ans = 0
        for i in range(n):
            if i in visits: continue
            c = dfs(i)
            ans += c * (n - c)
        return ans // 2

Yen-Chi ChenSat, Mar 25, 2023

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        ans = n * (n - 1) // 2
        graph = defaultdict(list)

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()

        def dfs(node):
            if node in visited:
                return 0

            visited.add(node)

            cnt = 1
            for nei in graph[node]:
                cnt += dfs(nei)
            return cnt

        components = []
        for node in range(n):
            if node not in visited:
                components.append(dfs(node))

        for k in components:
            ans -= k * (k - 1) // 2

        return ans

Ron ChenSat, Mar 25, 2023

Javascript

function countPairs(n, edges) {
  const graph = new Array(n).fill(0).map(() => []);
  for (const [v1, v2] of edges) {
    graph[v1].push(v2);
    graph[v2].push(v1);
  }

  const visited = new Array(n).fill(false);

  // 找出所有連通圖，並計算每個連通圖的節點數
  const graphNodes = [];
  for (let i = 0; i < n; i++) {
    if (visited[i]) continue;
    let count = 0;
    const stack = [i];
    while (stack.length) {
      const node = stack.pop();
      if (visited[node]) continue;
      visited[node] = true;
      count++;
      for (const v of graph[node]) {
        stack.push(v);
      }
    }

    graphNodes.push(count);
  }

  // 計算所有連通圖的組合數
  let ans = 0;
  for (let i = 0; i < graphNodes.length; i++) {
    for (let j = i + 1; j < graphNodes.length; j++) {
      ans += graphNodes[i] * graphNodes[j];
    }
  }

  return ans;
}

MarsgoatMar 26, 2023

Reference

回到題目列表