medium Count Unreachable Pairs of Nodes in an Undirected Graph

Problem Statement

You are given a positive integer n. You are also given undirected graph containing 0 to n - 1 nodes, and 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes aⁱ and bⁱ.

Return the count of unique node pairs where there's no path from one node to another.

Examples

Example 1:

• Input: n = 4, edges = [[0, 1], [2, 3]]

• Expected Output: 4
• Justification: The graph is divided into two disconnected parts: nodes 0 and 1 are connected, and nodes 2 and 3 are connected. The unreachable pairs are (0, 2), (0, 3), (1, 2), and (1, 3).

Example 2:

• Input: n = 5, edges = [[0, 1], [2, 3]]

• Expected Output: 8
• Justification: The unreachable pairs are (0, 2), (0, 3), (1, 2), (1, 3), (0, 4), (1, 4), (2, 4), and (3, 4).

Example 3:

• Input: n = 3, edges = []

• Expected Output: 3
• Justification: With no edges, every node is isolated. Hence, all possible pairs are unreachable from each other: (0, 1), (0, 2), and (1, 2).

Solution

To solve this problem, we'll leverage depth-first search (DFS) to identify all connected components within the graph. By knowing the size of each connected component, we can calculate how many pairs of nodes within the same component can reach each other. Since the problem asks for unreachable pairs, we'll subtract the count of reachable pairs from the total possible pairs in the graph.

This approach is effective because it directly identifies the sizes of isolated sections in the graph, making it straightforward to compute the unreachable pairs by using combinatorial mathematics. The use of DFS ensures that we can efficiently traverse and mark all nodes in a connected component, thereby accurately calculating each component's size.

Step-by-Step Algorithm with Detailed DFS Steps

1. Initialize Data Structures:

   • Create a HashMap called adj to store the adjacency list of the graph. This map associates each node with a list of its neighbors.
   • Initialize a boolean array named visit with a length of n (the number of nodes), with all elements set to false. This array tracks which nodes have been visited during DFS traversals.

2. Build the Graph (Adjacency List):

   • For each edge [u, v] in the edges array, do the following:
     • Add v to the adjacency list of u and u to the adjacency list of v. This step ensures that the graph correctly represents all connections (edges) between nodes.

3. Depth-First Search (DFS) to Find Component Sizes:

   • Define a recursive method dfs that takes a node node, the adjacency list adj, and the visited array visit. This method returns the size of the connected component that includes node.
   • Initialize a local variable count to 1, representing the current node.
   • Inside dfs, mark node as visited (visit[node] = true).
   • For each neighbor of node (accessible via adj.get(node)), if the neighbor has not been visited (!visit[neighbor]), recursively call dfs on the neighbor and add the result to count.
   • Return count at the end of dfs, representing the total size of the connected component found.

4. Calculate Unreachable Pairs:

   • Initialize two long variables: numberOfPairs to store the final result, and remainingNodes to track the number of nodes not yet included in any connected component, initially set to n.
   • Iterate over all nodes i from 0 to n - 1. For each node i:
     • If visit[i] is false (node i has not been visited), call the dfs method starting from i. This call explores the entire connected component containing i, marks all nodes within it as visited, and returns the size of this component.
     • Use the size returned by dfs to update numberOfPairs. The formula numberOfPairs += sizeOfComponent * (remainingNodes - sizeOfComponent) calculates the number of new unreachable pairs formed by the current component and updates numberOfPairs accordingly.
     • Subtract the size of the current component from remainingNodes to reflect the reduced number of nodes available for forming pairs.

5. Return the Total Number of Unreachable Pairs:

   • After iterating through all nodes and calculating unreachable pairs for each component, return numberOfPairs as the final result. This value represents the total number of pairs of nodes in the graph that cannot reach each other.

Algorithm Walkthrough

Let's consider the input: n = 5, edges = [[0, 1], [2, 3]].

1. Initialization:

   • adj is an empty map, and visit is an array of false values of length 5.

2. Build the Graph:

   • Add edge [0, 1] to adj: adj[0] now includes 1, and adj[1] includes 0.
   • Add edge [2, 3] to adj: adj[2] now includes 3, and adj[3] includes 2.

3. Count Unreachable Pairs:

   • Start with i = 0, numberOfPairs = 0, and remainingNodes = 5.
   • Since visit[0] is false, perform DFS from node 0:
     • Visit nodes 0 and 1, marking them as visited. The DFS returns 2, the size of this component.
     • Update numberOfPairs += 2 * (5 - 2) = 6.
     • Update remainingNodes -= 2, now remainingNodes = 3.
   • Continue with i = 1 to i = 2. Node 1 is already visited, so move to node 2:
     • Perform DFS from node 2, visiting nodes 2 and 3. The DFS returns 2.
     • Update numberOfPairs += 2 * (3 - 2) = 2.
     • Update remainingNodes -= 2, now remainingNodes = 1.
   • For i = 3 and i = 4, nodes 3 is already visited, and when i = 4, no DFS is performed as it's disconnected from others, implicitly counting as a single-node component that doesn't add to numberOfPairs since its potential pairs have already been counted.

4. Return Result:

   • The total numberOfPairs is (6 + 2 = 8), which is the final result returned by the method.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

  // DFS method to count the size of a connected component
  public int dfs(int node, Map<Integer, List<Integer>> adj, boolean[] visit) {
    int count = 1; // Count includes the current node
    visit[node] = true; // Mark current node as visited
    if (!adj.containsKey(node)) {
      return count; // If node has no neighbors, return count of 1
    }
    for (int neighbor : adj.get(node)) { // Iterate over neighbors
      if (!visit[neighbor]) { // If neighbor hasn't been visited
        count += dfs(neighbor, adj, visit); // Recursively visit and add to count
      }
    }
    return count; // Return total count of nodes in this component
  }

  // Method to count pairs of nodes that are unreachable from each other
  public long countPairs(int n, int[][] edges) {
    Map<Integer, List<Integer>> adj = new HashMap<>(); // Adjacency list representation of graph
    for (int[] edge : edges) { // Populate adjacency list
      adj.computeIfAbsent(edge[0], k -> new ArrayList<Integer>()).add(edge[1]);
      adj.computeIfAbsent(edge[1], k -> new ArrayList<Integer>()).add(edge[0]);
    }

    long numberOfPairs = 0; // To store result
    long sizeOfComponent = 0; // Size of the current connected component
    long remainingNodes = n; // Nodes that haven't been part of a counted component
    boolean[] visit = new boolean[n]; // Track visited nodes
    for (int i = 0; i < n; i++) { // Iterate over all nodes
      if (!visit[i]) { // If node i hasn't been visited
        sizeOfComponent = dfs(i, adj, visit); // Get size of its component
        numberOfPairs += sizeOfComponent * (remainingNodes - sizeOfComponent); // Update pairs count
        remainingNodes -= sizeOfComponent; // Decrease remaining nodes count
      }
    }
    return numberOfPairs; // Return total count of unreachable pairs
  }

  // Main method to test the algorithm with example inputs
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    System.out.println(
      solution.countPairs(4, new int[][] { { 0, 1 }, { 2, 3 } })
    ); // Expected: 4

    // Example 2
    System.out.println(
      solution.countPairs(5, new int[][] { { 0, 1 }, { 2, 3 } })
    ); // Expected: 8

    // Example 3
    System.out.println(solution.countPairs(3, new int[][] {})); // Expected: 3
  }
}

Complexity Analysis

Time Complexity

• DFS Traversal: The depth-first search (DFS) is performed for each node that hasn't been visited yet. Since each edge is visited exactly twice (once for each direction in the undirected graph), the time complexity for the DFS part is , where (V) is the number of vertices (nodes) and (E) is the number of edges in the graph.
• Building the Adjacency List: The adjacency list is built by iterating through each edge once, leading to a time complexity of for this step.

Overall, the time complexity of the algorithm is , accounting for both the construction of the adjacency list and the DFS traversal.

Space Complexity

• Adjacency List: The space complexity for storing the adjacency list is , as it needs to store a list of edges for each of the (V) vertices.
• Visit Array: An additional space is used to keep track of which nodes have been visited during DFS.
• DFS Call Stack: In the worst-case scenario, the depth of the call stack could be in the case of a deeply nested tree structure.

Hence, the total space complexity of the algorithm is , considering the storage requirements for the graph representation and the additional structures for managing DFS visits.