search

nagato1208 / nagato1208.github.io

For my blog
2 stars 0 forks source link

leetcode-1192-Critical Connections in a Network[tarjan求割边] | Nagato's blog #48

Open nagato1208 opened 5 years ago

nagato1208 commented 5 years ago

https://nagato1208.github.io/2019/09/15/leetcode-1192-Critical-Connections-in-a-Network-tarjan%E6%B1%82%E5%89%B2%E8%BE%B9/

描述给一个无向连通图, 求所有割边. (割边: 去掉这条边, 联通分量就会变成多个) 思路tarjan算法模板题. dfn数组表示正常dfs的遍历顺序(存的值可以看做时间戳), low数组表示该点不通过父节点能访问到的最小(时间戳)祖先节点. low[v] > dnf[u] 时, 说明v-u是割边.(可以这么想, 我们从v走到u, v之前有很多时间戳比v小的祖先节点, 现在从u出发不经过v,

Sakamono commented 5 years ago

感谢Z神！世界上最好的Z神！