#P11829. [TOIP2024] 棲息地分配
[TOIP2024] 棲息地分配
题目描述
有 隻貓活動於某個地區,每隻貓各有其棲息地,編號為 到 。棲息地之間有 條道路連接,道路總數不超過 。第 條道路連接第 個棲息地和第 個棲息地,貓可以沿著這些道路在棲息地之間雙向移動,且不會有兩條不同的道路連接著同一對棲息地。有 個動保團體要接管此地區,請你協助將這 個棲息地分配給這 個團體,滿足以下要求:
- 每個棲息地僅由 個團體管理,且每個團體需要管理至少 個棲息地。每個團體所屬的棲息地之間不一定要連通。
- 為了方便管理,每個團體會移除由該團體負責的棲息地之間的道路。換句話說,若有一條道路連接的兩個棲息地被分配到同一個團體,該道路會被移除。
- 這些道路移除後,剩餘的道路不可以形成「環」,以免貓可能會繞著環奔跑,讓工作人員難以捉捕。也就是說,不可以存在一個兩兩相異的棲息地序列 ,滿足 ,且對於所有 ,棲息地 和棲息地 都有一條未被移除的道路連接、同時 和 也有一條未被移除的道路連接。
舉例,有 個棲息地,道路連接如下圖所示
1
5 6
1 2
2 3
3 4
4 5
5 3
4 2
3 3 4 5
1 1
1 2
2
5 4
1 2
1 3
3 4
3 5
5 4
1 2
2 3
1 3
4 5
2 1 2
1 3
2 4 5
3 1 2 3
1 4
1 5