Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-03-24 18:02:08
1466. 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:
作者: a1234555 (肉宝宝)   2022-03-24 18:02:00
大师
作者: MurasakiSion (紫咲シオン)   2023-03-24 18:04:00
大师
作者: Che31128 (justjoke)   2023-03-24 18:10:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com