Count Unreachable Pairs Of Nodes In An Undirected Graph - Leetcode Solution

Problem Statement: Given an undirected graph with n vertices and m edges. Define a pair of nodes (i,j) as unreachable if there does not exist a path between node i and node j. Count the total number of such pairs in the given graph.

Input: The input for the problem contains two integers n and m, the number of vertices and the number of edges in the graph. This is followed by m lines containing two integers each, representing the two vertices that are connected by an edge.

Output: The output for the problem should contain a single integer denoting the total number of unreachable pairs of nodes in the given graph.

Solution: The first step is to represent the graph using an adjacency list. We create an array adj of size n, where adj[i] is a list of all nodes that are connected to node i. We use this representation in the following steps.

We then create an array visited of size n, initialized to false. We also create a variable cnt initialized to 0, which will store the count of unreachable pairs.

We then iterate through all the vertices and check if they have been visited. If not, we perform a depth-first search (DFS) starting from that node. During the DFS, we mark all the nodes that are reachable from the current node as visited.

After the DFS is complete, we compute the number of nodes that were not visited during the DFS. These nodes form a disjoint set with the visited nodes, i.e., there is no path between the visited and unvisited nodes.

We then compute the number of pairs that can be formed between the visited and unvisited nodes by multiplying the number of visited nodes with the number of unvisited nodes.

We add this count to cnt and repeat the process for all unvisited nodes.

Finally, we return cnt as the answer.

Time complexity: The time complexity of the above algorithm is O(n^2), where n is the number of vertices in the graph. This is because we perform a DFS for each unvisited node, which takes O(n) time. Within each DFS, we visit all the nodes connected to the current node, which takes O(n) time in the worst case. Therefore, the total time complexity is O(n^2).

Space complexity: The space complexity of the above algorithm is O(n+m), where n is the number of vertices and m is the number of edges. This is because we store the adjacency list, visited array, and cnt variable, which take O(n+m) space in total.

Code:

int cnt = 0;

void dfs(int u, vector<bool>& visited, vector<vector<int>>& adj) {
    visited[u] = true;
    for(int v : adj[u]) {
        if(!visited[v]) {
            dfs(v, visited, adj);
        }
    }
}

int countPairs(int n, int m, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for(auto& edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
    }
    vector<bool> visited(n, false);
    for(int u = 0; u < n; u++) {
        if(!visited[u]) {
            dfs(u, visited, adj);
            int visitedCount = count(visited.begin(), visited.end(), true);
            int unvisitedCount = n - visitedCount;
            cnt += visitedCount * unvisitedCount;
        }
    }
    return cnt;
}

The main function countPairs takes the number of vertices n, the number of edges m, and the list of edges as input and returns the count of unreachable pairs of nodes.

The adjacency list is constructed by iterating through all the edges and adding the respective nodes to each other's lists in adj.

We then iterate through all the nodes and call dfs on each node that has not been visited. Within dfs, we mark all the reachable nodes as visited.

After the DFS is complete, we compute the visitedCount and unvisitedCount and add visitedCount * unvisitedCount to cnt.

Finally, we return cnt as the answer.

1