Sponsored
Sponsored
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.
Time Complexity: O(n + e), where e is the number of edges, due to the union and find operations being amortized nearly constant.
Space Complexity: O(n), for storing parent, rank, and component sizes.
1using System;
2using System.Collections.Generic;
3
4class UnionFind {
5 private int[] parent, rank, size;
6 public UnionFind(int n) {
7 parent = new int[n];
8 rank = new int[n];
9 size = new int[n];
10 for (int i = 0; i < n; i++) {
11 parent[i] = i;
12 size[i] = 1;
13 }
14 }
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));
}
}Using C#'s UnionFind class helps to manage connected node components using find and union operations with path compression and rank optimization. After processing edges, unique roots are used to calculate unreachable pairs by component sizes.
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.
Time Complexity: O(n + e), where e is the number of edges, using DFS to discover components.
Space Complexity: O(n + e), due to adjacency list and visit tracking.
1def dfs(node, adj_list, visited):
2 stack = [node]
3 component_size = 0
4 while stack:
5 current = stack.pop()
6 if not visited[current]:
7 visited[current] = True
8 component_size += 1
9 for neighbor in adj_list[current]:
10 if not visited[neighbor]:
11 stack.append(neighbor)
12 return component_size
13
14
15def count_unreachable_pairs(n, edges):
16 adj_list = [[] for _ in range(n)]
17 for a, b in edges:
18 adj_list[a].append(b)
19 adj_list[b].append(a)
20
21 visited = [False] * n
22 total_pairs = n * (n - 1) // 2
23 reachable_pairs = 0
24
25 for i in range(n):
26 if not visited[i]:
27 component_size = dfs(i, adj_list, visited)
28 reachable_pairs += component_size * (component_size - 1) // 2
29
30 return total_pairs - reachable_pairs
31
32# Test Case
33n = 7
34edges = [[0, 2], [0, 5], [2, 4], [1, 6], [5, 4]]
35print(count_unreachable_pairs(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.