HAOI2006 （洛谷P2341)受歡迎的牛 題解

題目描述

友情鏈接原題

每頭奶牛都夢想成為牛棚里的明星。被所有奶牛喜歡的奶牛就是一頭明星奶牛。所有奶

牛都是自戀狂，每頭奶?？偸窍矚g自己的。奶牛之間的“喜歡”是可以傳遞的——如果A喜

歡B，B喜歡C，那么A也喜歡C。牛欄里共有N 頭奶牛，給定一些奶牛之間的愛慕關(guān)系，請你

算出有多少頭奶牛可以當(dāng)明星。

輸入輸出格式

輸入格式：

第一行：兩個用空格分開的整數(shù)：N和M

第二行到第M + 1行：每行兩個用空格分開的整數(shù)：A和B，表示A喜歡B

輸出格式：

第一行：單獨一個整數(shù)，表示明星奶牛的數(shù)量

輸入輸出樣例

輸入樣例#1：

3 3
1 2
2 1
2 3

輸出樣例#1：

1

說明

只有 3 號奶?？梢宰雒餍?/p>

【數(shù)據(jù)范圍】

10%的數(shù)據(jù)N<=20, M<=50

30%的數(shù)據(jù)N<=1000,M<=20000

70%的數(shù)據(jù)N<=5000,M<=50000

100%的數(shù)據(jù)N<=10000,M<=50000

題目分析

這是一道強(qiáng)連通分量的題

首先把樣例拿來畫一下（解決圖論題目常規(guī)操作），得到如下的圖：

image

我們可以發(fā)現(xiàn)一號和二號可以構(gòu)成一個強(qiáng)連通分量，然后就會想到tarjan縮點。。把一號和二號縮點后，可以得到如下的圖：

image

我們推論：縮點后出度為零的點為明星牛（假如出度為零的點是一個強(qiáng)連通分量的縮點，那么這個強(qiáng)連通分量中的所有牛都是明星牛）這個其實很好證，假如明星牛的出度不為0，它就會和其他點構(gòu)成一個強(qiáng)連通分量，那么就是縮點不徹底，而我們討論的是完全縮點后的情況。

我們在舉一個例子

image

縮點后的圖是這樣的

image

這兩個點都是出度為0，但是我們發(fā)現(xiàn)并沒有明星牛。原因是有兩個點出度為零。所以推論應(yīng)該改為：縮點后唯一的出度為0的點是明星牛，這樣也可以避免掉單獨的點帶來的影響。

假如這整個圖就是一個強(qiáng)連通圖，那么每一頭牛都是明星牛（縮點后只有一個點，仍然滿足推論）。

然后這個題就簡單了，算是裸的tarjan。

附上標(biāo)程

image