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.
1import java.util.*;
2
3public class CountUnreachablePairs {
4
5 static class UnionFind {
6 int[] parent, rank, size;
7
8 UnionFind(int n) {
9 parent = new int[n];
10 rank = new int[n];
11 size = new int[n];
12 Arrays.fill(size, 1);
13 for (int i = 0; i < n; i++)
14 parent[i] = i;
15 }
16
17 int find(int a) {
18 if (parent[a] != a)
19 parent[a] = find(parent[a]);
20 return parent[a];
21 }
22
23 void unionSets(int a, int b) {
24 int rootA = find(a);
25 int rootB = find(b);
26 if (rootA != rootB) {
27 if (rank[rootA] > rank[rootB]) {
28 parent[rootB] = rootA;
29 size[rootA] += size[rootB];
30 } else if (rank[rootA] < rank[rootB]) {
31 parent[rootA] = rootB;
32 size[rootB] += size[rootA];
33 } else {
34 parent[rootB] = rootA;
35 rank[rootA]++;
36 size[rootA] += size[rootB];
37 }
38 }
39 }
40 }
41
42 public static int countUnreachablePairs(int n, int[][] edges) {
43 UnionFind uf = new UnionFind(n);
44 for (int[] edge : edges) {
45 uf.unionSets(edge[0], edge[1]);
46 }
47 long totalPairs = (long)n * (n - 1) / 2;
48 long reachablePairs = 0;
49 for (int i = 0; i < n; i++) {
50 if (uf.find(i) == i) {
51 long c_size = uf.size[i];
52 reachablePairs += c_size * (c_size - 1) / 2;
53 }
54 }
55 return (int)(totalPairs - reachablePairs);
56 }
57
58 public static void main(String[] args) {
59 int n = 7;
60 int[][] edges = {{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}};
61 System.out.println(countUnreachablePairs(n, edges));
62 }
63}This Java implementation uses an internal UnionFind class to manage nodes and their connections. The find and union functions are implemented for path compression and union by rank. After processing the edges, the number of unreachable pairs is computed using the sizes of different 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.
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.
1import java.util.*;
2
3public class CountUnreachablePairsDFS {
4
5 public static void dfs(int node, boolean[
This Java version transforms nodes and edges into adjacency lists for component tracking using DFS. Connected components are formulated for each unvisited node, contributing size information to finalize unreachable pair calculations.