TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

40.0% (16/40)

Description

  主角威能。屢次阻止了黑色騎士團的第一野望,於是他們想出另種辦法。

  就是佔據一些城市,使得與城市相連的道路,都可以在他的控制之下。

  翻開大不列顛帝國的國土,你要找出黑色騎士團最少需要攻佔多少座城市

  並將結果報告回司令部,好讓司令部擬出對策,打破黑色騎士團的最終野望

Input Format

本題有多筆測試資料,請以EOF作為結束。(測試資料不超過十組)

第一行為兩個數字,n,m分別代表有幾個城市,幾條道路

(0≦n≦20,0≦m≦200)

接著有m行,每行兩個數字,st,ed分別代道路兩端連結的城市編號。

(0≦st,ed≦n-1)

Output Format

輸出黑色騎士團完成野望最小需要攻佔多少城市。

Sample Input

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

Sample Output

2

Hints

Problem Source

原TIOJ1375 / (最小頂點覆蓋) Problem Setter:ggm

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144