HAOI2006 （洛谷P2341)受欢迎的牛 题解

题目描述

友情链接原题

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入输出格式

输入格式：

第一行：两个用空格分开的整数：N和M

第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式：

第一行：单独一个整数，表示明星奶牛的数量

输入输出样例

输入样例#1：

3 3
1 2
2 1
2 3

输出样例#1：

1

说明

只有 3 号奶牛可以做明星

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

题目分析

这是一道强连通分量的题

首先把样例拿来画一下（解决图论题目常规操作），得到如下的图：

image

我们可以发现一号和二号可以构成一个强连通分量，然后就会想到tarjan缩点。。把一号和二号缩点后，可以得到如下的图：

image

我们推论：缩点后出度为零的点为明星牛（假如出度为零的点是一个强连通分量的缩点，那么这个强连通分量中的所有牛都是明星牛）这个其实很好证，假如明星牛的出度不为0，它就会和其他点构成一个强连通分量，那么就是缩点不彻底，而我们讨论的是完全缩点后的情况。

我们在举一个例子

image

缩点后的图是这样的

image

这两个点都是出度为0，但是我们发现并没有明星牛。原因是有两个点出度为零。所以推论应该改为：缩点后唯一的出度为0的点是明星牛，这样也可以避免掉单独的点带来的影响。

假如这整个图就是一个强连通图，那么每一头牛都是明星牛（缩点后只有一个点，仍然满足推论）。

然后这个题就简单了，算是裸的tarjan。

附上标程

image