mediumGraphsPattern: DFS

Node Depth Count Solution

Problem Statement

Given an adjacency list representation of a graph, count the number of nodes that can be reached from a given node using depth-first search.

Examples

Example 1:

Input:{1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]} 1

Output:4

Explanation: Starting from node 1, we can reach nodes 2 and 3. From node 2, we can reach 4. Thus, nodes 1, 2, 3, and 4 are all reachable.

Example 2:

Input:{10: [20, 30], 20: [10, 30], 30: [10, 20]} 10

Output:3

Explanation: Starting from node 10, we can reach nodes 20 and 30. All nodes (10, 20, 30) are reachable.

Example 3:

Input:{0: [], 1: [2, 3], 2: [1, 3], 3: [1, 2]} 1

Output:3

Explanation: Starting from node 1, we can reach nodes 2 and 3. Thus, nodes 1, 2, and 3 are all reachable.

Constraints

The graph is represented as an adjacency list.
The input graph is non-empty.
Each node is reachable from a given node.
Depth-first search is performed from a given node.
The function should return the total number of nodes reachable.

Time: O(n) Space: O(n)

Use a recursive depth-first search approach with a stack to optimize performance.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

def node_depth_count(graph_str, start_node_str):
    import ast
    graph = ast.literal_eval(graph_str)
    start_node = int(start_node_str)
    
    visited = set()
    count = 0

    def dfs(node):
        nonlocal count
        visited.add(node)
        count += 1
        if node in graph:
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

    dfs(start_node)
    return str(count)