Akira的OI(咸鱼)圈

Akira的OI(咸鱼)圈

过气算法竞赛选手的个人博客

[P2661]信息传递

这题的题意是将每个人及其信息传递对象抽象成一个有向图,最大传递次数即为最小环的长度。我们可以先用拓扑排序找环,显然的,不断拓扑后环上的每一个点的入度均不为零。因此我们可以用DFS求环的长度,访问过的点打上标记,不再求已经访问过的环的长度,以此降低时间复杂度。

Akira
来打小方呀~
FRIENDS
洛谷 vijos NUAAOJ