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]; g[a].add(b); g[b].add(a); } 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): vis.add(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).