AAlgoLoopSpaced repetition for LeetCode
MEDIUMBFS / DFSLeetCode ↗

Reorder Routes to Make All Paths Lead to the City Zero

The key idea

The n cities and n - 1 roads form a tree if you ignore direction. Walk outward from city 0 over that undirected tree; every road you cross in its original forward direction points away from 0 and must be reversed. Count those.

Problem

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network forms a tree). Last year, the ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [a, b] means a road from city a to city b.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city. Your task is to reorient some roads such that each city can visit city 0. Return the minimum number of edges changed.

It is guaranteed that each city can reach city 0 after reorder.

Constraints

Examples

Input: n = 3, connections = [[1,0],[2,0]] Output: 0
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] Output: 3
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] Output: 2

Complexity

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

See the full solution

410310
Step-by-step visualization
Start free →

More BFS / DFS problems