Coding - Reorder Routes to Make All Paths Lead to the City Zero

Here is the complete problem statement for "Coding - Reorder Routes to Make All Paths Lead to the City Zero" asked at Uber:

Problem Statement: There are n cities numbered from 0 to n-1, and n-1 roads connecting each pair of cities. You need to rearrange the roads such that there is exactly one path from city 0 to any other city. You don't need to change the direction of the roads.

The input is a 2D array m where m[i] = [a, b] means there is a road between city a and b. You need to return the number of reorderingings that satisfy the condition.

Examples:

1. Example 1: Input: n = 4, m = [[0,1],[1,2],[3,2]] Output: 2 Explanation: There are two ways to rearrange the roads: 0 -> 0 -> 1 -> 2 0 -> 2 -> 1 -> 3

2. Example 2: Input: n = 3, m = [[1,2],[2,0]] Output: 1

Constraints:

• 1 <= n <= 100
• 0 <= m.length < n * n
• 0 <= a, b < n

Hints:

1. Use a graph or adjacency list representation to model the roads.
2. Perform a depth-first search (DFS) or breadth-first search (BFS) to find the number of reorderingings.
3. Use a visited array to keep track of visited cities.

Solution: `python from collections import deque

def minReorder(n, connections): graph = [[] for _ in range(n)] for a, b in connections: graph[a].append(b)

visited = [False] * n
ans = 0
q = deque([0])
visited[0] = True

while q:
    node = q.popleft()
    for neighbor in graph[node]:
        if not visited[neighbor]:
            q.append(neighbor)
            visited[neighbor] = True
    if node != 0:
        ans += 1
    for neighbor in graph[node]:
        if not visited[neighbor]:
            graph[neighbor].remove(node)

return ans

` This solution uses a BFS approach to traverse the graph and count the number of reorderingings. It maintains a visited array to keep track of visited cities and a queue to store the next node to visit. The time complexity is O(n + m), where n is the number of cities and m is the number of roads.