Skip to content

Latest commit

 

History

History
 
 

2204.Distance-to-a-Cycle-in-Undirected-Graph

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2204.Distance-to-a-Cycle-in-Undirected-Graph

常规的拓扑排序。我们首先将所有度为1的点放入队列,按照层级遍历的顺序BFS:每弹出一个节点A,就考察其邻接节点并将度减去1,如果邻接节点度降为了1,就将其加入队列。持续BFS直至队列为空。

此时所有未曾访问的点都一定是在环上。我们再将这些点作为初始点放入队列中,重新开始BFS,就可以得到所有非环节点距离环的最短距离。