威风镰鼬

题解

/ 注册

全部文章 / 题解（共1篇）

题解 | #[NOIP2015]信息传递#

思路这道题的大意就是要我们求最小环的长度。我们知道这是一个n个顶点n条边的图，所以每一块最多只有一个环，并保证图中有环。我们可以从任意一个点开始搜索，如果碰到了原来记录过的顶点，那么就记录答案并跳出。如果下一个点已经被记录过了并且不是同一次搜索，那么直接跳出就好了。这个是一个O(n)的做法。代码...

dfs 普及组图论环

2021-06-22

1 523