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
如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)