#2316
Count Unreachable Pairs of Nodes in an Undirected Graph
specialist · 870 · lc medium +31 · verified · 49.8% accepted · 2,259 likes · top 37%
Description
You are given an integer n and an undirected graph with n nodes numbered 0 to n - 1. The graph is described by a 2D integer array edges where edges[i] = [ai, bi] represents an edge between ai and bi.
Return the number of pairs of distinct nodes that cannot reach each other through the graph.
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.
Code
1
2
3