HAOI2006 （洛谷P2341)受歡迎的牛 題解
題目描述
友情鏈接原題
每頭奶牛都夢想成為牛棚里的明星住册。被所有奶牛喜歡的奶牛就是一頭明星奶牛耘成。所有奶
牛都是自戀狂谓传，每頭奶牛總是喜歡自己的聘殖。奶牛之間的“喜歡”是可以傳遞的——如果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 號奶偶食耍可以做明星
【數(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
題目分析
這是一道強連通分量的題
首先把樣例拿來畫一下（解決圖論題目常規(guī)操作），得到如下的圖：
我們可以發(fā)現(xiàn)一號和二號可以構(gòu)成一個強連通分量衔肢，然后就會想到tarjan縮點庄岖。。把一號和二號縮點后角骤，可以得到如下的圖：
我們推論：縮點后出度為零的點為明星牛（假如出度為零的點是一個強連通分量的縮點隅忿，那么這個強連通分量中的所有牛都是明星牛）這個其實很好證，假如明星牛的出度不為0邦尊，它就會和其他點構(gòu)成一個強連通分量背桐，那么就是縮點不徹底，而我們討論的是完全縮點后的情況蝉揍。
我們在舉一個例子
縮點后的圖是這樣的
這兩個點都是出度為0链峭，但是我們發(fā)現(xiàn)并沒有明星牛。原因是有兩個點出度為零又沾。所以推論應(yīng)該改為：縮點后唯一的出度為0的點是明星牛弊仪，這樣也可以避免掉單獨的點帶來的影響。
假如這整個圖就是一個強連通圖杖刷，那么每一頭牛都是明星牛（縮點后只有一個點励饵，仍然滿足推論）。
然后這個題就簡單了滑燃，算是裸的tarjan役听。
附上標(biāo)程
