1375 . 黑色騎士團的最終野望
TopCoder
Tags
Description
主角威能。屢次阻止了黑色騎士團的第一野望，於是他們想出另種辦法。
就是佔據一些城市，使得與城市相連的道路，都可以在他的控制之下。
翻開大不列顛帝國的國土，你要找出黑色騎士團最少需要攻佔多少座城市
並將結果報告回司令部，好讓司令部擬出對策，打破黑色騎士團的最終野望
Input Format
本題有多筆測試資料，請以EOF作為結束。(測試資料不超過十組)
第一行為兩個數字，n，m分別代表有幾個城市，幾條道路
(0≦n≦20，0≦m≦200)
接著有m行，每行兩個數字，st，ed分別代道路兩端連結的城市編號。
(0≦st，ed≦n-1)
Output Format
輸出黑色騎士團完成野望最小需要攻佔多少城市。
Sample Input 1
5 5
0 4
1 2
1 4
2 4
4 3
0 4
1 2
1 4
2 4
4 3
Sample Output 1
2
Hints
Problem Source
原TIOJ1375 / (最小頂點覆蓋) Problem Setter：ggm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |