2597

$QAQ$，人生第一道紫题 我觉得还是只讲讲思路吧。毕竟我的代码太丑了。 先来看样例  这里为什么要反向存图呢？因为高级捕食者要捕食低级捕食者（生产者）。如果所有指向他的点（低级捕食者）都没了。他也肯定会死。 然后接着下看。 如果我们只用赤果果的topsort+递推。节点4（下同）就会卡掉你。 我们怎么改进呢？ 我们可以将节点4复制一份~~影分身！~~ 再利用边的有向性。建一颗树。 如图  这样的话我们就将问题转换为求以 节点x 为根的子树的节点的个数，再去一个重。 可是这样的话，最难的问题就变成了去重。 我们先等一等。再想一想4和4* 的性质只有节点1死了。4才会死尽。 而节点1是什么呢？是4和4* 的最近公共祖先。  我们可以利用一个类似并查集的思想，舍弃一些信息。使维护起来更加方便。 而这些信息。对于我们就不需要了。我们只关心i没了以后j是否会没。 就像这个样子 [](http://www.cnblogs.com/Lance1ot/) 我们再回看样例  我们在topsort建树中，扫描到了4。 根据我们之前找的道理。我们需要找**他们**的最近公共祖先并且链上去。 一个很简单的性质。对于样例，我们只需要找出2,3（就是在我们第2个图没有缩点之前中4和4* 的父亲，图2是我们为了理解的一个过程的树），就是所有指向他的节点在我们以及建好了的树中（无影分身版）的lca。 最终，最后一个在coding中的问题也解决了。 代码还是看楼下大佬吧