1256 . 砲打皮皮4

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

97.5% (78/80)

Submission's AC Ratio

64.2% (174/271)

Tags

CKinfor XXI-CKinfor

Description

好不容易闖過了多道困難的關卡，終點就在眼前了，沒想到前方又突然出現了許多的皮皮擋住去路。這次皮皮不再是存在於棋盤上，而是聚成一團，並且許多皮皮之間會手牽著手（不要懷疑，皮皮會變形術，要有幾隻手就有幾隻手）。
皮皮只要牽手就可以進行能量交流，並且自由聚集力量，而你發現，若場上有 N 隻皮皮，只要聚集 N−1 之皮皮的力量，就可以抵禦包含強者物質在內的任何攻擊，現在 Jimmy 提供了一個外掛程式，可以直接抹殺掉一隻皮皮，但是因為你只有試用版（正式版要錢啊！），只能使用一次，請問哪幾隻皮皮一旦被你抹殺掉之後，你就可以殲滅他們了？

Input Format

輸入可能包含多筆測試資料。每筆測試資料的第一行有兩個正整數 N,M 代表皮皮的個數和握手對數（1≤N≤10000，1≤M≤100000）。
接下來的 M 行每行有兩個正整數 A,B，表示編號 A 和編號 B 的皮皮有牽手。（1≤A,B≤N）
當 N=M=0 時，代表輸入結束，聰明的你當然不會對它輸出任何資料。

Output Format

請先輸出 Case #N: 表示這是第 N 筆輸出。
接著請輸出有幾個皮皮是可以被消滅的，並且由小到大輸出他們的編號，如果沒有皮皮被消滅後可以分裂他們的話，請輸出 0。

Sample Input 1

3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 5
1 4
4 3
1 2
2 3
3 4
0 0

Sample Output 1

Case #1:0 0
Case #2:1 4
Case #3:2 2 3

Hints

Problem Source

原TIOJ1256 / INFOR 21st幹部考(prob L)。Problem Setter：peter50216。
2021.03.30 Update: Added LATEX by FHVirus

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
Submit
Back to Top