Problem Description

You have an undirected graph with n nodes labeled from 0 to n - 1. The graph's connections are given as a list of edges, where each edge [ai, bi] represents an undirected connection between nodes ai and bi.

Your task is to find how many pairs of nodes cannot reach each other. Two nodes are considered unreachable from each other if there is no path connecting them through the edges in the graph.

For example, if you have nodes in separate connected components (isolated groups of connected nodes), any node from one component cannot reach any node from a different component. You need to count all such unreachable pairs.

The solution uses depth-first search (DFS) to identify connected components in the graph. The key insight is that nodes within the same connected component can all reach each other, but nodes in different components cannot.

The algorithm works by:

1. Building an adjacency list representation of the graph from the edges
2. Using DFS to find each connected component and count its size t
3. For each new component found, calculating the unreachable pairs as s * t, where s is the total number of nodes in all previously found components
4. Adding the current component's size to the running total s

This approach efficiently counts all unreachable pairs by recognizing that each node in a new component forms an unreachable pair with every node in all previously processed components.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly involves an undirected graph with n nodes and edges connecting them.

Is it a tree?

• No: The graph is not necessarily a tree. It can have multiple disconnected components, and there's no guarantee of a single connected acyclic structure.

Is the problem related to directed acyclic graphs?

• No: The problem deals with an undirected graph, not a directed one.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between nodes. We're identifying which nodes cannot reach each other at all.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - specifically finding pairs of nodes that are not connected (unreachable from each other).

Disjoint Set Union

• While DSU could solve this problem, the given solution uses DFS instead. Both approaches work for connectivity problems.

Alternative path through small constraints:

• The problem can also be solved with DFS by exploring each connected component, which is what the solution implements.

Conclusion: The flowchart leads us to connectivity problems, which can be solved using either DSU or DFS. The provided solution uses DFS to identify connected components and count unreachable pairs by tracking the size of each component and calculating cross-component pairs.

Intuition

The key insight is recognizing that in an undirected graph, nodes can be grouped into connected components. Within each connected component, all nodes can reach each other through some path. However, nodes in different components have no path between them - they are unreachable from each other.

Think of it like islands in an ocean. People on the same island can walk to meet each other, but people on different islands cannot reach each other without a bridge. We need to count how many pairs of people are on different islands.

When we find a connected component of size t, we need to count how many unreachable pairs this component creates with all previously discovered components. If we've already found components with a total of s nodes, then each of the t nodes in the current component forms an unreachable pair with each of the s nodes from previous components. This gives us s * t new unreachable pairs.

For example, if we have three components with sizes 3, 2, and 4:

• When we process the first component (size 3), there are no previous nodes, so no pairs yet
• When we process the second component (size 2), each of its 2 nodes pairs with each of the 3 nodes from the first component: 3 * 2 = 6 pairs
• When we process the third component (size 4), each of its 4 nodes pairs with each of the 5 nodes from previous components: 5 * 4 = 20 pairs
• Total: 0 + 6 + 20 = 26 unreachable pairs

This approach avoids double-counting because we only count pairs between the current component and all previous ones, never counting the same pair twice. DFS naturally helps us explore each component fully before moving to the next one.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution implements DFS to find connected components and calculate unreachable pairs efficiently.

Graph Representation: First, we build an adjacency list g from the edge list. For each edge [a, b], we add b to g[a] and a to g[b] since the graph is undirected.

DFS Function: The dfs(i) function explores a connected component starting from node i:

• If the node is already visited (vis[i] is True), return 0
• Mark the node as visited
• Recursively visit all neighbors and count the total nodes in this component
• Return 1 (current node) plus the sum of all nodes found through neighbors

Main Algorithm:

1. Initialize a visited array vis of size n with all False values
2. Initialize ans = 0 (total unreachable pairs) and s = 0 (cumulative nodes processed)
3. For each node i from 0 to n-1:
   • Call dfs(i) to get the component size t
   • If t > 0 (meaning this is a new unvisited component):
     • Add s * t to ans (pairs between this component and all previous ones)
     • Add t to s (update the cumulative count)

Why This Works:

• Each call to dfs(i) that returns a non-zero value represents a new connected component
• The multiplication s * t counts all pairs where one node is from the current component (size t) and the other is from any previous component (total size s)
• By processing components one by one and only counting pairs with previous components, we avoid double-counting
• The visited array ensures each node is processed exactly once

Time Complexity: O(n + m) where n is the number of nodes and m is the number of edges, as we visit each node and edge once.

Space Complexity: O(n) for the adjacency list, visited array, and recursion stack.

Example Walkthrough

Let's walk through a small example with 7 nodes and edges: [[0,1], [0,2], [3,4], [5,6]]

This creates a graph with three connected components:

• Component 1: nodes {0, 1, 2}
• Component 2: nodes {3, 4}
• Component 3: nodes {5, 6}

Step 1: Build adjacency list

g[0] = [1, 2]
g[1] = [0]
g[2] = [0]
g[3] = [4]
g[4] = [3]
g[5] = [6]
g[6] = [5]

Step 2: Initialize variables

• vis = [False, False, False, False, False, False, False]
• ans = 0 (unreachable pairs count)
• s = 0 (cumulative nodes processed)

Step 3: Process each node

Processing node 0:

• dfs(0) explores nodes 0→1→2, returns t = 3
• Since this is the first component, s = 0
• Add to answer: ans += 0 * 3 = 0
• Update cumulative: s = 0 + 3 = 3
• vis = [True, True, True, False, False, False, False]

Processing nodes 1, 2:

• Already visited, dfs returns 0, skip

Processing node 3:

• dfs(3) explores nodes 3→4, returns t = 2
• Current s = 3 (nodes from first component)
• Add to answer: ans += 3 * 2 = 6 (each of 2 nodes pairs with each of 3 previous nodes)
• Update cumulative: s = 3 + 2 = 5
• vis = [True, True, True, True, True, False, False]

Processing node 4:

• Already visited, skip

Processing node 5:

• dfs(5) explores nodes 5→6, returns t = 2
• Current s = 5 (nodes from first two components)
• Add to answer: ans += 5 * 2 = 10
• Update cumulative: s = 5 + 2 = 7
• vis = [True, True, True, True, True, True, True]

Processing node 6:

• Already visited, skip

Final Result: ans = 0 + 6 + 10 = 16 unreachable pairs

We can verify this: Component 1 (3 nodes) can't reach Component 2 (2 nodes) = 3×2 = 6 pairs. Component 1 can't reach Component 3 (2 nodes) = 3×2 = 6 pairs. Component 2 can't reach Component 3 = 2×2 = 4 pairs. Total = 6 + 6 + 4 = 16 pairs.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm performs a depth-first search (DFS) to identify connected components in the graph. Breaking down the operations:

• Building the adjacency list from edges takes O(m) time, where we iterate through all m edges and add each edge twice (once for each direction).
• The DFS traversal visits each node exactly once across all DFS calls, contributing O(n) time.
• For each node visited, we explore all its adjacent edges. Since each edge is represented twice in the adjacency list (undirected graph), we traverse a total of 2m edges across all DFS operations, which is O(m).
• The calculation of pairs (ans += s * t and s += t) is done n times with O(1) operations each.

Therefore, the total time complexity is O(n + m).

Space Complexity: O(n + m)

The space usage consists of:

• The adjacency list g stores all edges. Since it's an undirected graph, each edge is stored twice, requiring O(2m) = O(m) space.
• The visited array vis uses O(n) space to track visited nodes.
• The recursion stack for DFS can go up to O(n) depth in the worst case (e.g., a linear chain of nodes).
• Other variables (ans, s, t, i) use O(1) space.

Therefore, the total space complexity is O(n + m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Large Graphs

Problem: When calculating nodes_processed * component_size, the multiplication can overflow for large graphs. In the worst case with n=10^5 nodes split into two components, you could have approximately (50000 * 50000) = 2.5 * 10^9 pairs, which exceeds 32-bit integer limits in some languages.

Solution: In Python, this isn't an issue due to arbitrary precision integers, but in languages like Java or C++, use long/long long data types:

# Python handles this automatically, but in other languages:
# Java: long totalPairs = 0L;
# C++: long long totalPairs = 0;

2. Forgetting Bidirectional Edge Addition

Problem: Since the graph is undirected, each edge needs to be added in both directions. A common mistake is adding only one direction:

# WRONG - only adds one direction
for node_a, node_b in edges:
    adjacency_list[node_a].append(node_b)

Solution: Always add both directions for undirected graphs:

# CORRECT - adds both directions
for node_a, node_b in edges:
    adjacency_list[node_a].append(node_b)
    adjacency_list[node_b].append(node_a)

3. Stack Overflow with Deep Recursion

Problem: For graphs with very long paths (like a chain of n nodes), the recursive DFS can cause stack overflow. Python's default recursion limit is around 1000.

Solution: Either increase the recursion limit or use iterative DFS:

# Option 1: Increase recursion limit
import sys
sys.setrecursionlimit(10**6)

# Option 2: Iterative DFS
def dfs_iterative(start):
    if visited[start]:
        return 0
  
    stack = [start]
    component_size = 0
  
    while stack:
        node = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        component_size += 1
      
        for neighbor in adjacency_list[node]:
            if not visited[neighbor]:
                stack.append(neighbor)
  
    return component_size

4. Misunderstanding the Counting Logic

Problem: Attempting to count all pairs at once using combination formula C(n,2) - connected_pairs, or trying to count pairs within each component separately and summing them up.

Solution: Stick to the incremental approach where each new component's nodes form pairs with all previously processed nodes. This naturally avoids double-counting and correctly calculates cross-component pairs.