2316. Count Unreachable Pairs of Nodes in an Undirected Graph

MediumDepth-First SearchBreadth-First SearchUnion FindGraph
Leetcode Link

Problem Description

In this task, we are presented with an undirected graph defined by n nodes numbered from 0 to n - 1. The graph's connectivity is provided as an array, edges, where each element consists of a pair of integers that represent an undirected edge between two nodes in the graph. Our goal is to determine the number of node pairs that are unreachable from each other. Specifically, we must find all the pairs of different nodes where there is no path from one node to the other within the graph.

To visualize this, you could picture a set of islands (nodes) connected by bridges (edges). We are trying to count how many pairs of islands cannot be traveled between directly or indirectly.

Intuition

The approach to solving this problem involves understanding how connected components in an undirected graph work. A connected component is a subgraph where any two nodes are connected to each other by paths, and which is connected to no additional nodes in the supergraph. Essentially, all nodes within a connected component can reach each other, but they cannot reach nodes in other connected components.

By traversing the graph and determining the size of each connected component, we can calculate the number of unreachable pairs. The idea is that if a connected component has t nodes, none of the nodes in this component can reach nodes in the rest of the graph, which we can denote as s nodes. The number of unreachable pairs involving nodes from this component would then be the product s * t.

For instance, suppose we have a connected component of 4 nodes, and there are 6 nodes not in this component. There can be no paths between any of the 4 nodes and the 6 outside nodes, giving us 4 * 6 = 24 unreachable pairs.

To implement this concept programmatically, depth-first search (DFS) is a fitting choice. DFS can be used to explore the graph from each node, marking visited nodes to avoid counting a connected component more than once.

The algorithm systematically goes through each node. If the node hasn't been visited yet, it gets passed to a depth-first search, which counts all nodes reachable from that starting node (i.e., the size of the connected component). Once we get the size t of a connected component, we can calculate the number of unreachable pairs with nodes outside this component (which we have kept track of in s), and add it to the answer. We then update s to include the nodes from the newly found connected component before moving on to the next unvisited node.

This method ultimately gives us the sum of unreachable pairs for each connected component in the graph, which is the desired result.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The solution to the problem uses a classical graph traversal method known as Depth-First Search (DFS). DFS is a recursive algorithm that starts at a node and explores as far as possible along each branch before backtracking. This is perfect for exploring and marking all nodes within a connected component.

Here's how the algorithm is implemented:

  1. An adjacency list representation of the graph g is created, which is a list of lists. For every edge (a, b) in the given list edges, we add node b to the list of node a and vice versa because the graph is undirected.

    1g = [[] for _ in range(n)]
2for a, b in edges:
3    g[a].append(b)
4    g[b].append(a)

  2. An array vis of boolean values is used to keep track of visited nodes. Initially, all nodes are unvisited, so they are set to False.

    1vis = [False] * n

  3. The solution defines a recursive function dfs that takes an integer i representing the current node. It checks if this node is already visited. If it is, the function returns 0 because it shouldn't be counted again. If not, it sets the current node as visited (True) and explores all its neighbors by recursively calling dfs(j) for every neighbor j.

    1def dfs(i: int) -> int:
2    if vis[i]:
3        return 0
4    vis[i] = True
5    return 1 + sum(dfs(j) for j in g[i])

    The dfs function returns 1 (for the current node) plus the sum of nodes that can be reached from it, giving us the total size of the connected component.

  4. The main body of the solution maintains two variables, ans and s. The ans variable holds the cumulative count of unreachable pairs, while s keeps track of the total number of nodes processed so far across connected components.

  5. The solution iterates over all nodes, and for each unvisited node, it calls dfs to get the size of its connected component. The product of the current connected component size t and the count of nodes processed so far s gives us the number of unreachable pairs with respect to the component starting at this node.

    1ans = s = 0
2for i in range(n):
3    t = dfs(i)
4    ans += s * t
5    s += t

  6. Finally, after iterating through all the nodes, ans will contain the total number of pairs of nodes that are unreachable from each other. This is returned as the final result.

The algorithm effectively partitions the graph into disconnected โ€œislandsโ€ (connected components) and calculates unreachable pairs by considering the complement of nodes for each component encountered.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we are given a graph with n = 5 nodes and the following edges: [[0, 1], [1, 2], [3, 4]].

This graph consists of two separate connected components:

  • Component 1: Nodes 0, 1, and 2 are connected (0โ†”1โ†”2).
  • Component 2: Nodes 3 and 4 are connected (3โ†”4).

Using the approach described above, we will determine the number of pairs of nodes that are unreachable from each other.

  1. We create an adjacency list for our graph:
1g = [[1], [0, 2], [1], [4], [3]]
  1. Initialize a visited list with False showing none of the nodes is visited:
1vis = [False, False, False, False, False]

  1. We define our DFS function dfs. During the DFS process, this function will return the number of connected nodes for each connected component in the graph.

  2. We start traversing the nodes and applying DFS:

    • When we apply DFS to node 0, it will visit nodes 1 and 2 since they are connected. After the DFS call, visited becomes [True, True, True, False, False].

    • The size t of this component is 3. The s is initialized to 0, so ans becomes 0 * 3 = 0.

    • We update s to s + t which becomes 3.

  3. Node 1 and 2 are already visited, so our loop moves on to node 3. DFS on node 3 will visit node 4. visited becomes [True, True, True, True, True].

    • The size t of this second component is 2. Now s = 3 (from the previous step), and we update ans to ans + (s * t) which becomes 0 + (3 * 2) = 6.

    • Update s again to s + t which is now 5.

  4. Our ans is 6, which represents the total number of pairs of nodes that can't be reached from each other, which corresponds to the pairs (0,3), (0,4), (1,3), (1,4), (2,3), and (2,4).

After iterating through all nodes, the ans variable contains the correct number of unreachable node pairs, which is 6 in this case.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countPairs(self, n: int, edges: List[List[int]]) -> int:
5        # Depth First Search function to count nodes in a connected component
6        def dfs(node: int) -> int:
7            if visited[node]:
8                return 0
9            visited[node] = True
10            # Count current node + all nodes reachable from current node
11            return 1 + sum(dfs(neighbor) for neighbor in graph[node])
12
13        # Initialize the graph as an adjacency list
14        graph = [[] for _ in range(n)]
15        for node1, node2 in edges: # Build undirected graph
16            graph[node1].append(node2)
17            graph[node2].append(node1)
18      
19        visited = [False] * n # Track visited nodes
20      
21        # Main logic to count pairs
22        answer = total_nodes_visited = 0
23        for i in range(n):
24            component_size = dfs(i) # Size of connected component for node i
25            answer += total_nodes_visited * component_size # Multiply with size of previously found components
26            total_nodes_visited += component_size # Update total nodes visited after exploring component
27      
28        # Return the total number of pairs
29        return answer
30
1class Solution {
2
3    // Graph represented by an adjacency list
4    private List<Integer>[] graph;
5    // Visited array to keep track of visited nodes during DFS
6    private boolean[] visited;
7
8    // Method to count the number of pairs that can be formed
9    public long countPairs(int n, int[][] edges) {
10        graph = new List[n];
11        visited = new boolean[n];
12        // Initialize adjacency lists for each node
13        Arrays.setAll(graph, i -> new ArrayList<>());
14        // Build the graph by adding edges
15        for (int[] edge : edges) {
16            int a = edge[0], b = edge[1];
17            graph[a].add(b);
18            graph[b].add(a);
19        }
20
21        long answer = 0;
22        // Sum of component sizes found so far
23        long sumOfComponentSizes = 0;
24        // Traverse each node
25        for (int i = 0; i < n; ++i) {
26            // Perform a DFS from the node, count the size of the component
27            int componentSize = dfs(i);
28            // Update the answer with the product of component sizes
29            answer += sumOfComponentSizes * componentSize;
30            // Add the component size to the sum of component sizes
31            sumOfComponentSizes += componentSize;
32        }
33        return answer;
34    }
35
36    // Depth-first search to find component size
37    private int dfs(int currentNode) {
38        // If node is visited, return 0
39        if (visited[currentNode]) {
40            return 0;
41        }
42        // Mark the current node as visited
43        visited[currentNode] = true;
44        // Start with a count of 1 for the current node
45        int count = 1;
46        // Recur for all the vertices adjacent to this vertex
47        for (int nextNode : graph[currentNode]) {
48            count += dfs(nextNode);
49        }
50        // Return the size of the component
51        return count;
52    }
53}
54
1class Solution {
2public:
3    long long countPairs(int n, vector<vector<int>>& edges) {
4        // Create an adjacency list for the graph
5        vector<int> graph[n];
6        for (const auto& edge : edges) {
7            int from = edge[0], to = edge[1];
8            graph[from].push_back(to);
9            graph[to].push_back(from);
10        }
11      
12        // Create a visited array to keep track of visited nodes
13        vector<bool> visited(n, false);
14      
15        // Define a depth-first search (DFS) lambda function to count nodes in a component
16        function<int(int)> dfs = [&](int node) {
17            if (visited[node]) {
18                return 0; // If already visited, terminate this path
19            }
20            visited[node] = true; // Mark this node as visited
21            int count = 1; // Start count with the current node itself
22            for (int neighbor : graph[node]) {
23                count += dfs(neighbor); // Recursively visit neighbors and add to the count
24            }
25            return count;
26        };
27      
28        long long answer = 0;   // Initialize the answer to 0
29        long long sumOfCounts = 0; // Initialize the running sum of counts to 0
30      
31        // Iterate through each node in the graph
32        for (int i = 0; i < n; ++i) {
33            int componentSize = dfs(i); // Get the size of the component via DFS
34            answer += sumOfCounts * componentSize; // Add to the answer the product of current sum of counts and component size
35            sumOfCounts += componentSize; // Update the running sum of counts with the size of this component
36        }
37      
38        // Return the final answer, the total count of pairs
39        return answer;
40    }
41};
42
1// Function to count the number of reachable pairs in the undirected graph,
2// where n is the total number of nodes and edges is a list of edges connecting the nodes.
3function countPairs(n: number, edges: number[][]): number {
4    // Create an adjacency list to represent the graph.
5    const graph: number[][] = Array.from({ length: n }, () => []);
6
7    // Populate the adjacency list with bidirectional edges.
8    for (const [node1, node2] of edges) {
9        graph[node1].push(node2);
10        graph[node2].push(node1);
11    }
12
13    // Array to track visited nodes to prevent revisiting.
14    const visited: boolean[] = Array(n).fill(false);
15
16    // Depth-first search function to count connected nodes.
17    const depthFirstSearch = (node: number): number => {
18        // If the node is already visited, return 0 to avoid counting it again.
19        if (visited[node]) {
20            return 0;
21        }
22
23        // Mark the current node as visited.
24        visited[node] = true;
25
26        // Start with a count of 1 for the current node.
27        let count = 1;
28
29        // Recursively visit all connected nodes and increment count.
30        for (const connectedNode of graph[node]) {
31            count += depthFirstSearch(connectedNode);
32        }
33
34        // Return the count of nodes in the connected component.
35        return count;
36    };
37
38    // Initialize the answer to 0 and sum to keep track of the number of nodes visited so far.
39    let answer = 0;
40    let sum = 0;
41
42    // Iterate over each node to calculate the number of reachable pairs.
43    for (let i = 0; i < n; ++i) {
44        // Get the count of nodes in the connected component starting from node i.
45        const connectedNodes = depthFirstSearch(i);
46
47        // Update the answer with the number of pairs formed between the current
48        // connected component and the previously processed nodes.
49        answer += sum * connectedNodes;
50
51        // Update the sum with the number of nodes in the current connected component.
52        sum += connectedNodes;
53    }
54
55    // Return the final count of reachable pairs in the graph.
56    return answer;
57}
58
Not Sure What to Study? Take the 2-min Quiz๏ผš

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily determined by the depth-first search (dfs) function and the construction of the graph g.

  • Constructing the graph g involves iterating over all edges, which takes O(m) time where m is the total number of edges.
  • The dfs function will visit each node exactly once. Since an edge is considered twice (once for each of its endpoints), the dfs calls contribute O(n + m) time, where n is the total number of nodes.
  • The main loop (for i in range(n)) iterates n times and calls dfs during its iterations.

Combining these steps, the total time complexity is O(n + m) strictly speaking, as it accounts for the time to build the graph and the time to perform the DFS across all nodes and edges.

Space Complexity

The space complexity of the algorithm is influenced by the space needed to store the graph and the vis array.

  • The graph g is an adjacency list representation of the graph, which can consume up to O(n + m) space since each edge connects two nodes, and it is stored twice.
  • The vis array contains one boolean per node, contributing O(n) space.

Adding these up, the total space complexity is O(n + m) which comes from the adjacency list and the vis array.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ