【NOIP2015】信息传递

一个简单的找最小环问题。

首先我们可以根据每个人的信息传递对象构建一个每个点的出度都为1的有向图,那么一个人的生日会随着有向边不断传递下去,每轮游戏传递一条边,那么可以发现游戏总共进行的次数即找图中的最小环。

那么可以直接DFS了。用一个布尔数组vis记录该点是否走过,一个dep数组记录该点所在链中的深度。每次DFS一个没有走过的点,如果发现要搜索的下一个点已经存在深度,说明存在环,环的大小即为dep[now]-dep[next]+1。如果下一个点已经走过,但不存在深度,则说明在下一个点已经搜索结束,且其后链中没有点会回到当前点,也就是说不存在环,就可以直接结束。每DFS一个点完将dep还原至0,防止对之后的搜索造成干扰。

(不过因为每个点出度都为1,似乎直接while就可以了,出度更大的话就得用DFS了)

由于每个点只会被DFS一遍,时间复杂度为O(n)。

说点什么

  Subscribe  
提醒