easyTreesPattern: DFS
Reachable Roads Count Solution
Problem Statement
Given an adjacency list representation of a tree where each node represents an intersection and each edge represents a road, calculate the total number of roads reachable from a given intersection using a depth-first search algorithm.
Examples
Example 1:
Input:graph = {
1: [[2, 3], [3]],
2: [[1, 2], [3, 4, 5]],
3: [[1, 3], [2, 4]],
4: [[2, 3, 5], [3]],
5: [[2, 4]]}
Output:9
Explanation: The given graph has 9 roads reachable from the intersection represented by node 1.
Example 2:
Input:graph = {
1: [],
2: [[1]],
3: [],
4: [],
5: []}
Output:1
Explanation: The given graph has 1 road reachable from the intersection represented by node 1.
Example 3:
Input:graph = {
1: [[2], [3]],
2: [[1], [3]],
3: [[1], [2]]}
Output:4
Explanation: The given graph has 4 roads reachable from the intersection represented by node 1.
Constraints
- The input graph will represent a valid tree.
- The number of nodes in the graph will be in the range 1 to 10,000.
- Each edge in the graph will have a non-negative weight.
Time: O(n + e) Space: O(n)
An optimized approach would involve using a depth-first search algorithm to traverse the graph and count the number of roads reachable from the intersection.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def reachableRoadsCount(graph, start):
count = 0
visited = set()
def dfs(node):
visited.add(node)
count += 1
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
dfs(start)
return count