NOIP2015改善组Day1第二个问题，找到解决方案报告和分发说明。

被一个魔芋zrw

1.题目的一般描述(因为写的时候题目还没放出来)

几个朋友都在发自己的信息(生日)，每个朋友只会把自己知道的信息发给唯一的一个，但是他可以收到很多信息，收到信息后会在下一轮发给唯一的一个(暗恋233333)，问多少轮后会收到他当初发的信息。

输入:第一行是整数n，表示有n个人。

接下来的n行，每一行都有一个数字J，设这是除了第一行以外的第I行，那么J表示第I个人只会把信息传递给第J个人。

输出:一个整数，表示你的信息至少要经过几个回合才会回到你的手中。

样本输入:

五

2 4 2 3 1

样本输出:

三

数据比例:100% n<

2.需要什么样的算法？

根据数据规模，我们可以大致判断需要多少个高效的算法，有时甚至可以猜出这个问题用的是什么算法。对于这个题目，60%大概是O (n 2)算法，通常是赤裸裸的暴力回溯或者暴力广泛搜索，floyd的(我从NOIP吧看到的)也有用。

如果需要AC，算法的效率至少要在O(nlogn)以下(这里log是基于2而不是10)。

不过这个问题有一个O(n)算法，下面会讨论。

我们来画一张图(可能很丑，但是看着还可以)

画个图就知道自己在做什么了。

以样本数据为例:

我们很容易发现，2，3，4形成一个环，而1，5是没有用的...

因此，在环234中，因为每一轮都可以将在上一轮中已知的信息发送给唯一的下一个人，所以在环234中，需要三轮来发送信息。

多画画(因为我比较懒，只画了一个比较特殊情况的小图):

(有种你的圈子真乱的感觉。)

我们可以看到1，5，6，变成了一个环，2，3，4，8，也变成了一个环，7，9，是打酱油的。

所以对于这两个环，因为每一轮都可以把上一轮的信息传递给下一个人，所以很明显是1，5，6，传递的比较早，三轮。

说白了就是找图中最小的环。

4.ABCD，你选哪个？

所以有各种各样的最短路径算法来解决这个问题，但是我觉得时间复杂度还是需要研究的。老实说，我不知道这些算法能不能交流。例如，在SPFA算法中，最初O(kE)k是常数，大约等于2，E是边的数量。这里估计是O(nkE)，也就是O(nE)，因为每个点只会指向一条边，所以边是N，也就是O (n 2)，不优化很可能爆炸(请注意我的措辞)。

贴吧上也有人说是平行搜索集，据说是AC启用的，但不知道他打算怎么做。我觉得应该很难理解。

说白了，还是要走这条路。

有一点很清楚，因为一个人只会把信息传递给唯一的另一个人，我们可以用一维数组来存储这种关系。设数组为father[]，那么father[i]表示第I个人可以发送信息给第I个人，这样就节省了访问的空间和时间。

6.那么问题来了...

开凿者...哦不，哪个是最好的优化技术？

可能很多人都被困在这里了。

所以我们来翻出样本数据来看看:

有没有感觉这张图越看越难受？)

如果说每个点都受制于SPFA，弗洛伊德的最短路径算法，那么1，5这两个路人根本没用！而且，对于2，3，4来说，如果每个人都走一圈的话，是非常耗时的。

你得想一想，但是官方有100种获取数据的方法让你无法AC！

但是很明显，如果用一个数组来记录这个点是否被人去过，如果从路人的戒指中发现，岂不是很悲剧？

7.酱油，垃圾，扔了！

如何去掉酱油是一个大问题，但是你需要知道酱油是什么才能处理好。

没办法成环的点就是酱油！

那么怎么才能不形成环呢？

沙比，没人给他信息，他肯定只有自己的信息，没有办法形成环，比如5:

如果没用，那为什么还要留着？放下枪。

然后你会发现1也是打酱油的，然后摔:

感动2。2的穿透不为0，所以不执行操作。

结果，这就成了一枚完美的戒指。

说白了就是把初始渗透度为0的点删除，把所指点的渗透度减一。如果减法后指向点的穿透力也是0，那么继续按照刚才的操作，直到找到一个减法后穿透力不为0的点。

对于一些比我弱的人来说:

in-degree:在图中，对于某一点，通向该点的边的数量是In-degree。同样，相对度是从这个点到另一个点的边数。例如，在样本中，5的入度为0，出度为1；1的入度为1，出度为1；2的入度是2，出度是1。

当然，设置一个visit[]数组来表示这个点是否被访问过也是一个不错的选择，因为后面会用到。将深度为0的点的访问设置为已被访问。

对于刚才的第二种图形，我也做这个处理，得到的图形是这样的:

你感觉好多了吗？)

如果你还是不明白，看看下面的一小段:

"

我的想法是看2 4 2 3 1。

发现第五个人没有收到消息。

所以我测试了他

此时1也没有收到消息。

所以1也是t。

只剩下两三四个人了。

所以输出3

”——引用贴吧ID的诗人埃里克比较通俗的话。

对于删除点和边，dfs(深度优先搜索)和bfs(广度优先搜索)都可以，效率应该相差不大。我喜欢装逼排队，所以用了广搜。

最坏的情况，n=200000，1点对2，2点对3...一路199998点19999，199999点200000，200000点19999，o(。

好了，“酱油”的问题解决了，剩下的就是集中精力解决最小环问题了。

8.参观阵列创造奇迹

要知道，总会有一个不经意的细节影响结果。这就是旗帜的力量。

所以，屎可以乱，旗不能立。

↑以上都是扯淡。

首先我先说一下，因为贴吧的一个朋友(嗯，上面引用的人)知道前面的算法，但是因为没有学太多图论算法，所以不会玩最小环，我就拿出来说一下。

说实话，很多图论的算法我都没学过→ _→

我刚才也说了，用父亲一维数组保存这个图非常省空间省时间。

所以就是找到度数不为0的点(其实到这个时候应该只剩下度数为1的点了，因为每个点只能在一个环里，所以可以画几个图来证明)，然后用父数组调用环(这个类似于并行搜索集)。

但是，如果每找到一个点就调用一次环，最坏的情况是O(n ^ 2)。

那约定好的O(nlogn)呢？

不打不打，探望有什么好处？谁合适就给谁！

对于样本，在访问了点2和环2、3、4之后，点3和4都被访问过，因为同一个环的长度必须相同，所以不需要再次搜索点3和4。

然后使用访问数组记录该点是否被访问过。在访问一个环时，每次访问一个点，你都会把它标记为已访问，下次循环到这个点时可以跳过它，节省时间。

这就是为什么刚才渗透率为0的点需要设置为已经访问过的点——不能打酱油。

最差情况:n=200000，1点对2，2点对3...199999指向200000，200000指向1。

For循环:n次

搜索时:n次

或O(n)

9.摘要

前几年改进组day1的第二个话题我做过一些题，但我觉得这次应该是最容易的了(不过这次我不会写第三个话题，看特殊数据只会骗30分)，也就是说大家会靠明天的话题得分(FJ某党立了个旗说如果有人在FJ AC第三个话题就直播)。

我觉得，真的，画图是这个问题的关键(我记得我以前的竞赛老师王老师经常说一件事就是数形结合)。多画图，多模拟，很容易找到解决问题的方法。我太弱了，总要花1个小时左右，不到半个小时才能做完一两道题。个人认为这个算法应该算是这个问题中效率最高的算法之一，因为除了最后的搜索之外，没有重复计算的地方。而且应该是最容易理解的算法，所以AC应该没有问题。至于其他算法，我太弱了，听不懂。

对了，我附上了被大神贴出后的脸截图作为反例(代码也是后面放的):