Count Unreachable Pairs of Nodes in an Undirected Graph solution and explanation
Google
9 more videos on this problem
Count Unreachable Pairs of Nodes in an Undirected Graph | Leetcode - 2316 | MICROSOFT | Live CodingcodestorywithMIK · 28:24 · 8K views
Count Unreachable Pairs of Nodes in an Undirected Graph || DFS || MathsAryan Mittal · 17:26 · 2K views
2316. Count Unreachable Pairs of Nodes in an Undirected Graph (Leetcode Medium)Programming Live with Larry · 10:04 · 1K views
Daily Leetcode #1089: Mar 25, 2023 - 2316. Count Unreachable Pairs of Nodes in an Undirected GraphProgramming Live with Larry · 10:19 · 709 views
LeetCode #2316 | Count Unreachable Pairs of Nodes in an Undirected GraphCode Meant · 12:35 · 515 views
Leetcode 2316 【Google】. Count Unreachable Pairs of Nodes in an Undirected Graph - Union-Find methodCode-Yao · 13:08 · 401 views
LeetCode 2316 - Count Unreachable Pairs of Nodes in an Undirected Graph [Daily Challenge]Code with Carter · 17:41 · 350 views
Count Unreachable Pairs of Nodes in an Undirected Graph - Leetcode 2316 - PythonLit Code · 10:01 · 207 views
Count Unreachable Pairs of Nodes in an Undirected Graph| Leetcode 2316 | DFS | C++Tech Courses · 11:44 · 179 views
LeetCode | 2316. Count Unreachable Pairs of Nodes in an Undirected Graph | GRAPH | DFSCompl3x · 13:46 · 177 views
The 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 <= 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ai, bi < nai != bi- There are no repeated edges.
Approach overview
Problem Overview: You are given n nodes and an edge list describing an undirected graph. Two nodes are considered unreachable if no path exists between them. The task is to count how many pairs of nodes belong to different connected components.
The key observation: nodes inside the same connected component can reach each other, so only nodes from different components contribute to the answer. Once you know the size of each component, you can count cross-component pairs efficiently.
Approach 1: Union-Find to Identify Components (Time: O(n + m * α(n)), Space: O(n))
This method uses the Disjoint Set Union structure to group nodes into connected components while processing edges. For every edge (u, v), perform a union operation so both nodes share the same root. After processing all edges, iterate through nodes and count how many belong to each root component. If component sizes are s1, s2, s3..., the number of unreachable pairs can be computed incrementally by multiplying each size with the remaining nodes not yet processed. Union-Find with path compression and union by rank keeps operations almost constant time. This approach works well when edges arrive dynamically or when you already use Union Find in your workflow.
Approach 2: Depth-First Search to Explore Components (Time: O(n + m), Space: O(n))
Build an adjacency list for the graph, then iterate through all nodes. If a node has not been visited, run a DFS to explore its entire connected component and count its size. Each DFS traversal returns the number of nodes reachable from that start node. Similar to the union-find solution, use component sizes to accumulate unreachable pairs by multiplying the current component size with the number of remaining nodes. DFS naturally fits graph traversal problems and is easy to implement using recursion or a stack. This approach relies on standard Depth-First Search traversal on an undirected graph.
BFS works identically if you prefer a queue-based traversal using Breadth-First Search. Both DFS and BFS discover connected components in linear time.
Recommended for interviews: Both DFS and Union-Find achieve optimal O(n + m)-style performance. DFS is often quicker to implement during interviews because it only requires an adjacency list and a visited array. Union-Find demonstrates stronger knowledge of disjoint-set data structures and is useful when the problem involves repeated connectivity queries. Showing either approach signals solid graph fundamentals.
Approach 1: Union-Find to Identify Components
The Union-Find data structure can be used to efficiently determine connected components in the graph. By iterating over the edges and performing union operations, we can group nodes into their respective connected components. Once all edges are processed, nodes within the same connected component can reach each other, whereas nodes in different components cannot.
To count the number of unreachable pairs of nodes, compute the size of each component. If the total number of nodes is n, and the size of each component is c_i, the unreachable pairs are given by the sum of c_i * (n - c_i) for all components i.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
self.size = [1] * size
def find(self, a):
if self.parent[a] != a:
self.parent[a] = self.find(self.parent[a])
return self.parent[a]
def union(self, a, b):
rootA = self.find(a)
rootB = self.find(b)
if rootA != rootB:
if self.rank[rootA] > self.rank[rootB]:
self.parent[rootB] = rootA
self.size[rootA] += self.size[rootB]
elif self.rank[rootA] < self.rank[rootB]:
self.parent[rootA] = rootB
self.size[rootB] += self.size[rootA]
else:
self.parent[rootB] = rootA
self.rank[rootA] += 1
self.size[rootA] += self.size[rootB]
def componentSize(self, a):
root = self.find(a)
return self.size[root]
def count_unreachable_pairs(n, edges):
uf = UnionFind(n)
for a, b in edges:
uf.union(a, b)
total_pairs = n * (n - 1) // 2
reachable_pairs = 0
unique_roots = set(uf.find(i) for i in range(n))
for root in unique_roots:
c_size = uf.componentSize(root)
reachable_pairs += c_size * (c_size - 1) // 2
return total_pairs - reachable_pairs
# Example Usage
n = 7
edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
print(count_unreachable_pairs(n, edges))import java.util.*;
public class CountUnreachablePairs {
static class UnionFind {
int[] parent, rank, size;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
size = new int[n];
Arrays.fill(size, 1);
for (int i = 0; i < n; i++)
parent[i] = i;
}
int find(int a) {
if (parent[a] != a)
parent[a] = find(parent[a]);
return parent[a];
}
void unionSets(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
size[rootA] += size[rootB];
} else if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
size[rootB] += size[rootA];
} else {
parent[rootB] = rootA;
rank[rootA]++;
size[rootA] += size[rootB];
}
}
}
}
public static int countUnreachablePairs(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
uf.unionSets(edge[0], edge[1]);
}
long totalPairs = (long)n * (n - 1) / 2;
long reachablePairs = 0;
for (int i = 0; i < n; i++) {
if (uf.find(i) == i) {
long c_size = uf.size[i];
reachablePairs += c_size * (c_size - 1) / 2;
}
}
return (int)(totalPairs - reachablePairs);
}
public static void main(String[] args) {
int n = 7;
int[][] edges = {{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}};
System.out.println(countUnreachablePairs(n, edges));
}
}#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
class UnionFind {
public:
vector<int> parent, rank, size;
UnionFind(int n) : parent(n), rank(n, 0), size(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int a) {
if (parent[a] != a)
parent[a] = find(parent[a]);
return parent[a];
}
void unionSets(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
size[rootA] += size[rootB];
} else if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
size[rootB] += size[rootA];
} else {
parent[rootB] = rootA;
rank[rootA]++;
size[rootA] += size[rootB];
}
}
}
};
int countUnreachablePairs(int n, vector<vector<int>>& edges) {
UnionFind uf(n);
for (const auto &edge : edges) {
uf.unionSets(edge[0], edge[1]);
}
long totalPairs = (long)n * (n - 1) / 2;
long reachablePairs = 0;
for (int i = 0; i < n; ++i) {
if (uf.find(i) == i) {
long c_size = uf.size[i];
reachablePairs += c_size * (c_size - 1) / 2;
}
}
return totalPairs - reachablePairs;
}
int main() {
int n = 7;
vector<vector<int>> edges = {{0,2},{0,5},{2,4},{1,6},{5,4}};
cout << countUnreachablePairs(n, edges);
return 0;
}class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, index) => index);
this.rank = Array(n).fill(0);
this.size = Array(n).fill(1);
}
find(a) {
if (this.parent[a] !== a) this.parent[a] = this.find(this.parent[a]);
return this.parent[a];
}
union(a, b) {
const rootA = this.find(a);
const rootB = this.find(b);
if (rootA !== rootB) {
if (this.rank[rootA] > this.rank[rootB]) {
this.parent[rootB] = rootA;
this.size[rootA] += this.size[rootB];
} else if (this.rank[rootA] < this.rank[rootB]) {
this.parent[rootA] = rootB;
this.size[rootB] += this.size[rootA];
} else {
this.parent[rootB] = rootA;
this.rank[rootA]++;
this.size[rootA] += this.size[rootB];
}
}
}
componentSize(a) {
return this.size[this.find(a)];
}
}
function countUnreachablePairs(n, edges) {
const uf = new UnionFind(n);
for (const [a, b] of edges) {
uf.union(a, b);
}
let totalPairs = BigInt(n) * BigInt(n - 1) / 2n;
let reachablePairs = 0n;
const uniqueRoots = new Set(Array.from({length: n}, (_, i) => uf.find(i)));
for (const root of uniqueRoots) {
const c_size = uf.componentSize(root);
reachablePairs += BigInt(c_size) * BigInt(c_size - 1) / 2n;
}
return Number(totalPairs - reachablePairs);
}
// Example Usage
const n = 7;
const edges = [[0, 2], [0, 5], [2, 4], [1, 6], [5, 4]];
console.log(countUnreachablePairs(n, edges));#include <stdio.h>
#include <stdlib.h>
int find(int *parent, int a) {
if (parent[a] != a) {
parent[a] = find(parent, parent[a]);
}
return parent[a];
}
void unionSets(int *parent, int *rank, int a, int b) {
int rootA = find(parent, a);
int rootB = find(parent, b);
if (rootA != rootB) {
if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
} else if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
} else {
parent[rootB] = rootA;
rank[rootA]++;
}
}
}
int countUnreachablePairs(int n, int edges[][2], int edgesSize) {
int *parent = malloc(n * sizeof(int));
int *rank = malloc(n * sizeof(int));
int *componentSize = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
for (int i = 0; i < edgesSize; i++) {
unionSets(parent, rank, edges[i][0], edges[i][1]);
}
for (int i = 0; i < n; i++) {
componentSize[find(parent, i)]++;
}
long totalPairs = ((long)n * (n - 1)) / 2;
long reachablePairs = 0;
for (int i = 0; i < n; i++) {
if (componentSize[i] > 1) {
reachablePairs += ((long)componentSize[i] * (componentSize[i] - 1)) / 2;
}
}
free(parent);
free(rank);
free(componentSize);
return (int)(totalPairs - reachablePairs);
}
int main() {
int n = 7;
int edges[][2] = {{0,2},{0,5},{2,4},{1,6},{5,4}};
int edgesSize = 5;
printf("%d", countUnreachablePairs(n, edges, edgesSize));
return 0;
}using System;
using System.Collections.Generic;
class UnionFind {
private int[] parent, rank, size;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int Find(int a) {
if (parent[a] != a) parent[a] = Find(parent[a]);
return parent[a];
}
public void Union(int a, int b) {
int rootA = Find(a);
int rootB = Find(b);
if (rootA != rootB) {
if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
size[rootA] += size[rootB];
} else if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
size[rootB] += size[rootA];
} else {
parent[rootB] = rootA;
rank[rootA]++;
size[rootA] += size[rootB];
}
}
}
public int ComponentSize(int a) {
return size[Find(a)];
}
}
public class UnreachablePairs {
public static int CountUnreachablePairs(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
foreach (int[] edge in edges) {
uf.Union(edge[0], edge[1]);
}
long totalPairs = (long)n * (n - 1) / 2;
long reachablePairs = 0;
HashSet<int> uniqueRoots = new HashSet<int>();
for (int i = 0; i < n; i++) {
uniqueRoots.Add(uf.Find(i));
}
foreach (int root in uniqueRoots) {
int c_size = uf.ComponentSize(root);
reachablePairs += (long)c_size * (c_size - 1) / 2;
}
return (int)(totalPairs - reachablePairs);
}
public static void Main(string[] args) {
int n = 7;
int[][] edges = { new int[] {0, 2}, new int[] {0, 5}, new int[] {2, 4}, new int[] {1, 6}, new int[] {5, 4} };
Console.WriteLine(CountUnreachablePairs(n, edges));
}
}This implementation uses a custom UnionFind class in Python. Find and union operations ensure nodes are linked in their components, using path compression and union by rank techniques. Finally, the solution sums sizes of components to find unreachable node pairs.
Time Complexity: O(n + e) due to optimized Union-Find operations.
Space Complexity: O(n), necessary to store parent, rank, and component sizes.
Approach 2: Depth-First Search to Explore Components
Depth-first search (DFS) can also be employed to explore nodes and determine connected components. By traversing all nodes and initiating DFS for unvisited nodes, the graph's nodes can be segregated into connected sections. Each DFS run marks all connected nodes, constructing a component. Once the components are identified, calculating the number of unreachable pairs becomes straightforward.
The total number of pairs of nodes is (n * (n - 1)) / 2. Subtract the number of pairs within each component from this total to get the number of unreachable pairs.
def dfs(node, adj_list, visited):
stack = [node]
component_size = 0
while stack:
current = stack.pop()
if not visited[current]:
visited[current] = True
component_size += 1
for neighbor in adj_list[current]:
if not visited[neighbor]:
stack.append(neighbor)
return component_size
def count_unreachable_pairs(n, edges):
adj_list = [[] for _ in range(n)]
for a, b in edges:
adj_list[a].append(b)
adj_list[b].append(a)
visited = [False] * n
total_pairs = n * (n - 1) // 2
reachable_pairs = 0
for i in range(n):
if not visited[i]:
component_size = dfs(i, adj_list, visited)
reachable_pairs += component_size * (component_size - 1) // 2
return total_pairs - reachable_pairs
# Test Case
n = 7
edges = [[0, 2], [0, 5], [2, 4], [1, 6], [5, 4]]
print(count_unreachable_pairs(n, edges))import java.util.*;
public class CountUnreachablePairsDFS {
public static void dfs(int node, boolean[] visited, List<List<Integer>> adjList, int[] componentSize) {
visited[node] = true;
componentSize[0]++;
for (int neighbor : adjList.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, visited, adjList, componentSize);
}
}
}
public static int countUnreachablePairs(int n, int[][] edges) {
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
for (int[] edge : edges) {
adjList.get(edge[0]).add(edge[1]);
adjList.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
long totalPairs = (long)n * (n - 1) / 2;
long reachablePairs = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int[] componentSize = {0};
dfs(i, visited, adjList, componentSize);
reachablePairs += (long)componentSize[0] * (componentSize[0] - 1) / 2;
}
}
return (int)(totalPairs - reachablePairs);
}
public static void main(String[] args) {
int n = 7;
int[][] edges = {{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}};
System.out.println(countUnreachablePairs(n, edges));
}
}#include <iostream>
#include <vector>
using namespace std;
void dfs(int v, vector<int> &visited, vector<vector<int>> &adjList, int &componentSize) {
visited[v] = 1;
componentSize++;
for (int neighbor : adjList[v]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, adjList, componentSize);
}
}
}
int countUnreachablePairs(int n, vector<vector<int>>& edges) {
vector<vector<int>> adjList(n);
for (const auto &edge : edges) {
adjList[edge[0]].push_back(edge[1]);
adjList[edge[1]].push_back(edge[0]);
}
vector<int> visited(n, 0);
long totalPairs = (long)n * (n - 1) / 2;
long reachablePairs = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
int componentSize = 0;
dfs(i, visited, adjList, componentSize);
reachablePairs += (long)componentSize * (componentSize - 1) / 2;
}
}
return totalPairs - reachablePairs;
}
int main() {
int n = 7;
vector<vector<int>> edges = {{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}};
cout << countUnreachablePairs(n, edges);
return 0;
}function dfs(node, adjList, visited) {
let stack = [node];
let componentSize = 0;
while (stack.length > 0) {
let current = stack.pop();
if (!visited[current]) {
visited[current] = true;
componentSize++;
for (let neighbor of adjList[current]) {
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
}
return componentSize;
}
function countUnreachablePairs(n, edges) {
const adjList = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
adjList[a].push(b);
adjList[b].push(a);
}
const visited = Array(n).fill(false);
let totalPairs = BigInt(n) * BigInt(n - 1) / 2n;
let reachablePairs = 0n;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
const componentSize = dfs(i, adjList, visited);
reachablePairs += BigInt(componentSize) * BigInt(componentSize - 1) / 2n;
}
}
return Number(totalPairs - reachablePairs);
}
// Example usage:
const n = 7;
const edges = [[0, 2], [0, 5], [2, 4], [1, 6], [5, 4]];
console.log(countUnreachablePairs(n, edges));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void dfs(int node, int* componentSize, bool* visited, int** adjList, int* adjSize) {
visited[node] = true;
(*componentSize)++;
for (int i = 0; i < adjSize[node]; i++) {
int neighbor = adjList[node][i];
if (!visited[neighbor]) {
dfs(neighbor, componentSize, visited, adjList, adjSize);
}
}
}
int countUnreachablePairs(int n, int edges[][2], int edgesSize) {
int** adjList = (int**)malloc(n * sizeof(int*));
int* adjSize = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
adjList[i] = (int*)malloc(n * sizeof(int));
}
for (int i = 0; i < edgesSize; i++) {
int a = edges[i][0];
int b = edges[i][1];
adjList[a][adjSize[a]++] = b;
adjList[b][adjSize[b]++] = a;
}
bool* visited = (bool*)calloc(n, sizeof(bool));
long totalPairs = ((long)n * (n - 1)) / 2;
long reachablePairs = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int componentSize = 0;
dfs(i, &componentSize, visited, adjList, adjSize);
reachablePairs += ((long)componentSize * (componentSize - 1)) / 2;
}
}
for (int i = 0; i < n; i++) {
free(adjList[i]);
}
free(adjList);
free(adjSize);
free(visited);
return (int)(totalPairs - reachablePairs);
}
int main() {
int n = 7;
int edges[][2] = {{0,2},{0,5},{2,4},{1,6},{5,4}};
int edgesSize = 5;
printf("%d", countUnreachablePairs(n, edges, edgesSize));
return 0;
}using System;
using System.Collections.Generic;
public class CountUnreachablePairsDFS {
public static void Dfs(int node, bool[] visited, List<List<int>> adjList, ref int componentSize) {
Stack<int> stack = new Stack<int>();
stack.Push(node);
while (stack.Count > 0) {
int current = stack.Pop();
if (!visited[current]) {
visited[current] = true;
componentSize++;
foreach (int neighbor in adjList[current]) {
if (!visited[neighbor]) {
stack.Push(neighbor);
}
}
}
}
}
public static int CountUnreachablePairs(int n, int[][] edges) {
List<List<int>> adjList = new List<List<int>>();
for (int i = 0; i < n; i++) {
adjList.Add(new List<int>());
}
foreach (int[] edge in edges) {
adjList[edge[0]].Add(edge[1]);
adjList[edge[1]].Add(edge[0]);
}
bool[] visited = new bool[n];
long totalPairs = (long)n * (n - 1) / 2;
long reachablePairs = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int componentSize = 0;
Dfs(i, visited, adjList, ref componentSize);
reachablePairs += (long)componentSize * (componentSize - 1) / 2;
}
}
return (int)(totalPairs - reachablePairs);
}
public static void Main(string[] args) {
int n = 7;
int[][] edges = { new int[] {0, 2}, new int[] {0, 5}, new int[] {2, 4}, new int[] {1, 6}, new int[] {5, 4} };
Console.WriteLine(CountUnreachablePairs(n, edges));
}
}Python solution applies DFS iteratively with a stack, ensuring correct component sizes by marking visited nodes. Adjacency lists capture the graph, enabling unreachable node pair computation.
Time Complexity: O(n + e), effectively analyzing through DFS.
Space Complexity: O(n + e), based on adjacency list and stack usage.
Approach 3: DFS
For any two nodes in an undirected graph, if there is a path between them, then they are mutually reachable.
Therefore, we can use depth-first search to find the number of nodes t in each connected component, and then multiply the current number of nodes t in the connected component by the number of nodes s in all previous connected components to obtain the number of unreachable node pairs in the current connected component, which is s times t. Then, we add t to s and continue to search for the next connected component until all connected components have been searched, and we can obtain the final answer.
The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of nodes and edges, respectively.
function countPairs(n: number, edges: number[][]): number {
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number): number => {
if (vis[i]) {
return 0;
}
vis[i] = true;
let cnt = 1;
for (const j of g[i]) {
cnt += dfs(j);
}
return cnt;
};
let [ans, s] = [0, 0];
for (let i = 0; i < n; ++i) {
const 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 {
if vis[i] {
return 0
}
vis[i] = true
cnt := 1
for _, j := range g[i] {
cnt += dfs(j)
}
return cnt
}
var s int64
for i := 0; i < n; i++ {
t := int64(dfs(i))
ans += s * t
s += t
}
return
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find to Identify Components | Time Complexity: O(n + e) due to optimized Union-Find operations. |
| Depth-First Search to Explore Components | Time Complexity: O(n + e), effectively analyzing through DFS. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O(n + m * α(n)) | O(n) | Best when connectivity needs to be tracked dynamically or edges are processed incrementally |
| Depth-First Search (Component Counting) | O(n + m) | O(n) | Straightforward graph traversal when the full adjacency list is available |
| Breadth-First Search (Component Counting) | O(n + m) | O(n) | Preferred when iterative traversal with a queue is easier than recursion |
Frequently asked questions
Is Count Unreachable Pairs of Nodes in an Undirected Graph easy or hard?
The problem is rated Medium because the main challenge is recognizing that the task reduces to counting connected component sizes. Once that insight is clear, applying DFS, BFS, or Union-Find leads to a straightforward linear-time solution.
Count Unreachable Pairs of Nodes in an Undirected Graph Python/Java solution
Python and Java implementations typically build an adjacency list and run DFS or BFS to determine component sizes. Another option uses a Union-Find class to merge nodes while processing edges. Both implementations compute unreachable pairs using component size multiplication and run in O(n + m) time.
How to solve Count Unreachable Pairs of Nodes in an Undirected Graph in O(n)?
First compute connected component sizes using DFS, BFS, or Union-Find in O(n + m). If component sizes are s1, s2, s3, iterate through them and accumulate pairs using size * remaining_nodes. This avoids checking every pair explicitly and reduces the computation to linear time relative to the graph size.
What is the best approach for Count Unreachable Pairs of Nodes in an Undirected Graph?
The optimal solution identifies connected components and counts pairs across components. This can be implemented using Union-Find or DFS/BFS traversal. Both approaches run in O(n + m) time where n is the number of nodes and m is the number of edges. After computing component sizes, multiply each component size by the number of nodes remaining outside it to count unreachable pairs efficiently.
Is Count Unreachable Pairs of Nodes in an Undirected Graph asked at Google/Amazon/Meta?
Graph connectivity and component-counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involving Union-Find, connected components, or counting cross-component pairs are common in medium-level graph interview rounds.
What data structure is used in Count Unreachable Pairs of Nodes in an Undirected Graph?
The problem primarily uses graph data structures such as adjacency lists along with traversal algorithms like DFS or BFS. Another common structure is the Disjoint Set Union (Union-Find) data structure, which efficiently groups nodes into connected components.
What is the time complexity of Count Unreachable Pairs of Nodes in an Undirected Graph?
The optimal complexity is O(n + m), where n is the number of nodes and m is the number of edges. DFS or BFS visits each node and edge once. Union-Find also achieves near-linear complexity with path compression and union by rank, resulting in O(n + m * α(n)) which is effectively linear for practical input sizes.