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

推薦文章