Count Unreachable Pairs of Nodes in an Undirected Graph

Problem Statement

The task involves determining the number of pairs of nodes in an undirected graph that are unreachable from one another. An integer n represents the total number of nodes in the graph, which are numerically labeled from 0 to n-1. The graph's edges are provided as a list of pairs, each pair [ai, bi] indicating an undirected edge between nodes ai and bi. The primary goal is to compute how many distinct pairs of nodes do not have a path connecting them.

Examples

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 <= 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• There are no repeated edges.

Approach and Intuition

Given the problem's nature, let's break down the method to solve it through the following steps:

1. Interpret the graph structure from the edges.

   • Construct an adjacency list to represent the graph, which will efficiently store all nodes and their respective connections.

2. Identify connected components.

   • Use Depth First Search (DFS) or Breadth First Search (BFS) to explore the graph.
   • Start from any unvisited node and visit all reachable nodes to form a connected component.
   • Keep track of the nodes involved in each component.

3. Calculate the unreachable node pairs.

   • First, for each component, calculate the possible pairs within the component itself, ensuring that these pairs are reachable.
   • Compute the total possible pairs of nodes which is given by the formula: C(n, 2) = n * (n - 1) / 2, where n is the number of nodes.
   • The number of unreachable pairs can be found by subtracting the reachable pairs in all components from the total pairs.

4. Consider different scenarios:

   • All nodes connected: If all nodes are part of a single connected component, then every node is reachable from every other node, resulting in zero unreachable pairs.
   • Multiple connected components: If the graph contains multiple disjoint components, then nodes from different components will form unreachable pairs.

By reviewing the examples provided:

• In Example 1, all three nodes are connected hence there are no unreachable pairs.
• In Example 2, the graph is fragmented into different disjoint components, leading to 14 unreachable pairs calculated by checking inter-component connections.

Solutions

class DisjointSetUnion {
private:
    vector<int> parent, size;
    
public:
    DisjointSetUnion(int count) {
        parent.resize(count);
        size.resize(count, 0);
        for (int i = 0; i < count; i++) {
            parent[i] = i;
        }
    }
    int findParent(int node) {
        if (parent[node] != node) parent[node] = findParent(parent[node]);
        return parent[node];
    }
    void unite(int x, int y) {
        int rootX = findParent(x), rootY = findParent(y);
        if (rootX == rootY) {
            return;
        } else if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;
        } else if (size[rootX] > size[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            size[rootX]++;
        }
    }
};
    
class Solution {
public:
    long long calculatePairs(int m, vector<vector<int>>& relations) {
        DisjointSetUnion dsu(m);
        for (auto relation : relations) {
            dsu.unite(relation[0], relation[1]);
        }
        unordered_map<int, int> clusterCount;
        for (int i = 0; i < m; i++) {
            clusterCount[dsu.findParent(i)]++;
        }
    
        long long paths = 0;
        long long leftoverNodes = m;
        for (auto cluster : clusterCount) {
            int countInCluster = cluster.second;
            paths += countInCluster * (leftoverNodes - countInCluster);
            leftoverNodes -= countInCluster;
        }
        return paths;
    }
};