POJ 2186 Popular Cows -- tarjan 縮點

連結：

題意：

每一頭牛都希望在牛群裡面備受矚目，在一個牛群中有N頭牛（1<=N<=10000），你被給予M（1<=M<=50000）個關系對，形式如（A,B），這意味着A牛認為B牛比它更受歡迎，由于這種歡迎度是滿足傳遞性的，那麼若是A牛認為B牛更受歡迎，B牛認為C牛更受歡迎，那麼A牛也會認為C牛更受歡迎。你的任務是計算出被所有牛受歡迎的牛的個數。

輸入：

第一行兩個整數 N 和 M 第2 到 M + 1 行，兩個分開的數 A,B，意味着 A認為 B 更受歡迎。

輸出：

被所有牛認為受歡迎的牛的個數

比如輸入：

3 3 1 2 2 1 2 3

比如輸出：

1

隐藏資訊：

3号牛是最後歡迎的

來源于：

USACO 2007 秋季賽

思路：

用tarjan算法求得強連通分量後，将每個SCC縮點，得到的圖為 DAG 圖，然後尋找出度為 0 的節點（數出該分量中的節點個數），若出度為 0 的節點不止一個，則不存在答案。

Kosaraju算法解：