明年本科毕业刷题贴

https://www.youtube.com/watch?v=4NQ3HnhyNfQ

332. Reconstruct Itinerary
HierHolzer
条件： 必须存在解
DFS解题思路：
1. 对于当前图像建图，对于当前起点map里面存priorityQueue
2. 对于当前start point，dfs访问所有点直到pq为空。

微信用户_b99d1cc 发表于 2022-12-18 05:58
332. Reconstruct Itinerary
HierHolzer
条件： 必须存在解

1192. Critical Connections in a Network
DFS解法。
Critical Connections定义: 去掉当前边使图形成为两个不同的图形。
思路：
对于当前节点用DFS，记录当前步数和最低可访问的步数
初始化当前最低步数为当前步数
1.如果已经访问过当前nei节点，low[cur] = min(low[cur],disc[nei])
2.如果nei没被访问，dfs(nei)   low[cur] = min(low[nei],low[cur])
2-1 判断 low[nei] > disc[cur] if true， add to result
原理: 把low[nei]的值传递low[parent], 如果这个值小于当前步数，说明存在环，这种情况下去掉当前的边不会分割图形。 如果当前的low[nei] > disc[cur] 则说明当前边是critical。
Time:  O(V + E)
Space: O(V + E)

17, Letter Combinations of a Phone Number