楼主:
Rushia (みけねこ的鼻屎)
2023-03-24 18:02:081466. Reorder Routes to Make All Paths Lead to the City Zero
有n个城市,编号从0到n-1,有n-1条道路,道路由connections表示,其中
connections[i] = [ai, bi]表示从城市ai到城市bi的道路,每个城市
间只会有一条路可以走且是单行道。
城市0将举办一个活动,我们的任务是重新定向一些单行道,以便每个城市都能
够到达城市0。返回更改的最小边数,可以确保每个城市的道路改向后都能到达城市0。
Example :
https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node
can reach the node 0 (capital).
思路:
1.道路都是单行道不过我们可以先把整个图当作是一个无向图,从0开始出发做DFS,
检查下个目的地是否存在"往起点方向"的路径。
2.我们用负的值来表示反方向的目的地,如果下个目的地无法回到起点就让ans递增。
3.因为是无向图所以要记录上个点避免进入循环。
Java Code: