【BZOJ1051】【HAOI2006】受欢迎的牛

题意还是很明确的:给你一张有向图,问你有多少点能被其他所有点到达。

做法还是很巧妙的。

首先Tarjan肯定是要做的(虽然并不知道为什么但是感觉一定要做的样子)

那么Tarjan了之后有什么好处呢?

首先如果有一些点能被所有其他点到达那么他们一定是一个强连通分量里的,因为他们肯定能够互相到达。并且在这个强连通分量之外的点肯定不行。

是不是靠这一点就可以判断了呢?

考虑在Tarjan后产生了许多强连通分量,如果对于一个强连通分量,其他的强连通分量均指向他那么答案就是这个强连通分量中的点的个数。

那么成立的充要条件就是这个这个强连通分量没有出边,而其他强连通分量均有出边。

依此判断即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz