Unlike regular connectivity problems, we’re asked to handle a graph with directed edges. We need to find the number of edges that have to be reversed in order to make all edges lead to the 0th city. To intuitively solve this, we’ll conduct a depth-first search from the 0th node. Depth-first search is inherently directed away from the node it starts from.
We keep track of the edges present in the input, maintaining their direction. Each time we visit a node, we’re traveling away from the 0th node. So if we encounter an edge that’s traveling in the same direction, away, we know that this edge needs to be reversed - we increment our counter.
The solution is as follows:
from collections import defaultdict
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
roads = set()
graph = defaultdict(list)
for x, y in connections:
graph[x].append(y)
graph[y].append(x)
roads.add((x, y))
def dfs(node: int) -> int:
ans = 0
for neighbor in graph[node]:
if neighbor not in seen:
if (node, neighbor) in roads:
ans += 1
seen.add(neighbor)
ans += dfs(neighbor)
return ans
seen = {0}
return dfs(0)_ Time Complexity:
O(n) - We visit each node once.
_ Space Complexity:
O(n) - We maintain an adjaceny list.