Solution For Count Unreachable Pairs Of Nodes In An Undirected Graph

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& visited, vector>& adj) {
visited[u] = true;
for(int v : adj[u]) {
if(!visited[v]) {
dfs(v, visited, adj);
}
}
}

int countPairs(int n, int m, vector>& edges) {
vector> adj(n);
for(auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector 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.

Step by Step Implementation For Count Unreachable Pairs Of Nodes In An Undirected Graph

There are two possible solutions for this problem:

1) Use a Union-Find data structure to keep track of the connected components in the graph. For each edge in the graph, check if the two nodes are in the same component. If they are, then the edge is not reachable. If they are not, then union the two components.

2) Perform a DFS or BFS from each node in the graph. For each edge in the graph, check if the two nodes are in the same connected component. If they are, then the edge is not reachable.

def countUnreachablePairs(graph): 

# Initialize all nodes as not visited 
visited = [False] * len(graph) 

# Initialize count of reachable pairs as 0 
count = 0

# Do a DFS from every node one by one 
for i in range(len(graph)): 

# If node is not visited, then do DFS 
if not visited[i]: 

# Mark as visited 
visited[i] = True

# Call DFS for all its adjacent nodes 
for j in range(len(graph[i])): 
if not visited[graph[i][j]]: 
count += 1

# Return count of reachable pairs 
return count

Given an undirected graph with n nodes and m edges, return the number of pairs of nodes that are not connected by an edge.

// create a Set to store visited nodes
const visited = new Set();

// create a variable to store the number of pairs of nodes that are not connected by an edge
let pairs = 0;

// iterate over all nodes in the graph
for (let i = 0; i < n; i++) {
    // if the node has not been visited
    if (!visited.has(i)) {
        // iterate over all edges connected to the node
        for (let j = 0; j < m; j++) {
            // if the edge is not connected to the node
            if (graph[i][j] === 0) {
                // increment the number of pairs
                pairs++;
            }
            // mark the node as visited
            visited.add(i);
        }
    }
}

// return the number of pairs
return pairs;

There are many possible solutions to this problem. One approach would be to use a depth-first search algorithm to find all the reachable nodes from a given starting node, and then to count the number of pairs of nodes (x,y) such that x is reachable from the starting node but y is not.

The idea is to do a DFS from each node and keep track of the nodes visited in a hashset. For each node, we iterate through its neighbors and do a DFS from there. If the neighbor has not been visited, we add it to the hashset. At the end, the size of the hashset will be the number of nodes reachable from the starting node.