2023-03-25.md

题目

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.

思路

代码

// runtime 93.33% memory 86.67%
var countPairs = function(n, edges) {
  const parent = new Array(n).fill(-1)
  function find(x) {
    if (parent[x] < 0) {
      return x
    } else {
      parent[x] = find(parent[x])
      return parent[x]
    }
  }
  for (const [x, y] of edges) {
    const rootX = find(x)
    const rootY = find(y)
    if (rootX != rootY) {
      parent[rootX] += parent[rootY]
      parent[rootY] = rootX
    }
  }
  let count = 0
  for (const x of parent) {
    if (x < 0) {
      count += (n + x) * (-x)
    }
  }
  return count / 2
}