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.
1#include <iostream>
2#include <vector>
3#include <numeric>
4using namespace std;
5
6class UnionFind {
7public:
8 vector<int> parent, rank, size;
9 UnionFind(int n) : parent(n), rank(n, 0), size(n, 1) {
10 iota(parent.begin(), parent.end(), 0);
11 }
12 int find(int a) {
13 if (parent[a] != a)
14 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;
}This C++ solution uses a Union-Find class to maintain connected components. The find function implements path compression, and union uses union by rank technique. After processing all edges, it iterates over all nodes, sums up the sizes of connected components, and calculates unreachable pairs using c_i * (n - c_i).
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.