##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2316.html

# 2316. Count Unreachable Pairs of Nodes in an Undirected Graph

• Difficulty: Medium.
• Related Topics: Depth-First Search, Breadth-First Search, Union Find, Graph.
• Similar Questions: Number of Islands.

## Problem

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:

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 <= 105

• 0 <= edges.length <= 2 * 105

• edges[i].length == 2

• 0 <= ai, bi < n

• ai != bi

• There are no repeated edges.

## Solution (Java, C++, Python)

• class Solution {
public long countPairs(int n, int[][] edges) {
DSU d = new DSU(n);
HashMap<Integer, Integer> map = new HashMap<>();
for (int[] e : edges) {
d.union(e[0], e[1]);
}
long ans = 0;
for (int i = 0; i < n; i++) {
int p = d.findParent(i);
int cnt = map.containsKey(p) ? map.get(p) : 0;
ans += i - cnt;
map.put(p, map.getOrDefault(p, 0) + 1);
}
return ans;
}

private static class DSU {
int[] rank;
int[] parent;

DSU(int n) {
rank = new int[n + 1];
parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
}

int findParent(int node) {
if (parent[node] == node) {
return node;
}
parent[node] = findParent(parent[node]);
return findParent(parent[node]);
}

boolean union(int x, int y) {
int px = findParent(x);
int py = findParent(y);
if (px == py) {
return false;
}
if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[px] = py;
rank[py]++;
}
return true;
}
}
}

############

class Solution {
private boolean[] vis;
private List<Integer>[] g;

public long countPairs(int n, int[][] edges) {
vis = new boolean[n];
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (var e : edges) {
int a = e[0], b = e[1];
}
long ans = 0, s = 0;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
long t = dfs(i);
ans += s * t;
s += t;
}
}
return ans;
}

private int dfs(int i) {
vis[i] = true;
int cnt = 1;
for (int j : g[i]) {
if (!vis[j]) {
cnt += dfs(j);
}
}
return cnt;
}
}

• class Solution:
def countPairs(self, n: int, edges: List[List[int]]) -> int:
def dfs(i):
cnt = 1
for j in g[i]:
if j not in vis:
cnt += dfs(j)
return cnt

g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
vis = set()
ans = s = 0
for i in range(n):
if i not in vis:
t = dfs(i)
ans += s * t
s += t
return ans

############

# 2316. Count Unreachable Pairs of Nodes in an Undirected Graph
# https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/

class DSU:
def __init__(self, n):
self.graph = list(range(n))

def find(self, x):
if self.graph[x] != x:
self.graph[x] = self.find(self.graph[x])

return self.graph[x]

def union(self, x, y):
ux, uy = self.find(x), self.find(y)
self.graph[ux] = uy

def connected(self, x, y):
return self.find(x) == self.find(y)

def disconnect(self, x):
self.graph[x] = x

class Solution:
def countPairs(self, n: int, edges: List[List[int]]) -> int:
dsu = DSU(n)

for a, b in edges:
dsu.union(a, b)

parents = [0] * n

for node in range(n):
p = dsu.find(node)
parents[p] += 1

res = 0

for node in range(n):
p = dsu.find(node)
res += n - parents[p]

return res // 2


• class Solution {
public:
long long countPairs(int n, vector<vector<int>>& edges) {
vector<vector<int>> g(n);
for (auto& e : edges) {
int a = e[0], b = e[1];
g[a].emplace_back(b);
g[b].emplace_back(a);
}
vector<bool> vis(n);
function<int(int)> dfs = [&](int i) -> int {
vis[i] = true;
int cnt = 1;
for (int j : g[i]) {
if (!vis[j]) {
cnt += dfs(j);
}
}
return cnt;
};
long long ans = 0, s = 0;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
long long t = dfs(i);
ans += s * t;
s += t;
}
}
return ans;
}
};

• func countPairs(n int, edges [][]int) (ans int64) {
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
vis := make([]bool, n)
var dfs func(int) int
dfs = func(i int) int {
vis[i] = true
cnt := 1
for _, j := range g[i] {
if !vis[j] {
cnt += dfs(j)
}
}
return cnt
}
var s int64
for i := 0; i < n; i++ {
if !vis[i] {
t := int64(dfs(i))
ans += s * t
s += t
}
}
return
}

• function countPairs(n: number, edges: number[][]): number {
const g = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
const vis = new Array(n).fill(false);
const dfs = (i: number) => {
vis[i] = true;
let cnt = 1;
for (const j of g[i]) {
if (!vis[j]) {
cnt += dfs(j);
}
}
return cnt;
};
let ans = 0;
let s = 0;
for (let i = 0; i < n; ++i) {
if (!vis[i]) {
const t = dfs(i);
ans += s * t;
s += t;
}
}
return ans;
}


• impl Solution {
pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>) -> i64 {
let n = n as usize;
let mut g = vec![vec![]; n];
let mut vis = vec![false; n];
for e in edges {
let u = e[0] as usize;
let v = e[1] as usize;
g[u].push(v);
g[v].push(u);
}

fn dfs(g: &Vec<Vec<usize>>, vis: &mut Vec<bool>, u: usize) -> i64 {
if vis[u] {
return 0;
}
vis[u] = true;
let mut cnt = 1;
for &v in &g[u] {
cnt += dfs(g, vis, v);
}
cnt
}

let mut ans = 0;
let mut s = 0;
for u in 0..n {
let t = dfs(&g, &mut vis, u);
ans += t * s;
s += t;
}
ans
}
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).