TopCoder

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

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

37.0% (20/54)

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

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5