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[
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5void dfs(int node, int* componentSize, bool* visited, int** adjList, int* adjSize) {
6 visited[node] = true;
7 (*componentSize)++;
8 for (int i = 0; i < adjSize[node]; i++) {
9 int neighbor = adjList[node][i];
10 if (!visited[neighbor]) {
11 dfs(neighbor, componentSize, visited, adjList, adjSize);
12 }
13 }
14}
15
16int countUnreachablePairs(int n, int edges[][2], int edgesSize) {
17 int** adjList = (int**)malloc(n * sizeof(int*));
18 int* adjSize = (int*)calloc(n, sizeof(int));
19 for (int i = 0; i < n; i++) {
20 adjList[i] = (int*)malloc(n * sizeof(int));
21 }
22
23 for (int i = 0; i < edgesSize; i++) {
24 int a = edges[i][0];
25 int b = edges[i][1];
26 adjList[a][adjSize[a]++] = b;
27 adjList[b][adjSize[b]++] = a;
28 }
29
30 bool* visited = (bool*)calloc(n, sizeof(bool));
31 long totalPairs = ((long)n * (n - 1)) / 2;
32 long reachablePairs = 0;
33
34 for (int i = 0; i < n; i++) {
35 if (!visited[i]) {
36 int componentSize = 0;
37 dfs(i, &componentSize, visited, adjList, adjSize);
38 reachablePairs += ((long)componentSize * (componentSize - 1)) / 2;
39 }
40 }
41
42 for (int i = 0; i < n; i++) {
43 free(adjList[i]);
44 }
45 free(adjList);
46 free(adjSize);
47 free(visited);
48
49 return (int)(totalPairs - reachablePairs);
50}
51
52int main() {
53 int n = 7;
54 int edges[][2] = {{0,2},{0,5},{2,4},{1,6},{5,4}};
55 int edgesSize = 5;
56 printf("%d", countUnreachablePairs(n, edges, edgesSize));
57 return 0;
58}This C approach constructs an adjacency list for the graph and uses DFS to explore all nodes in each component and count their sizes. Unvisited nodes initiate new DFS runs to mark nodes as part of a connected component. The number of unreachable pairs is calculated accordingly