Uva 10685 - Nature

題目

Problem#

大自然存在著食物鏈,體型大的動物吃小動物,小動物吃植物,死亡的動物被分解,作為植物的養分。
而你的任務是給定一組動物,求出最大的食物鏈動物數量為何?假如A吃B,你可以認定它們在同個食物鏈裡。

輸入#

每筆測資開頭有兩個整數 $C$ 代表有幾隻動物和 $R$ 有幾組關係;接著 $C$ 列,每列有一個名字(字串、只有小寫、不超過30字);再接著有 $R$ 列,每列有兩個名字,代表第二個動物吃第一個動物。
你可以認定沒有一隻動物是自己的獵食者。
輸入終止在 $C = R = 0$ ,每筆測資間有空白列。

$1 \le C \le 5000$
$0 \le R \le 5000$

輸出#

對於每筆測資,最大組的食物鏈的大小。

想法#

disjoint set題,每個動物名稱用 map<string, int> 對應到一個 int,接著就照著輸入合併組,然後找最大的整數。

AC Code#

https://github.com/roy4801/solved_problems/blob/master/uva/10685.cpp