Phủ đỉnh (vertex cover) là tập đỉnh sao cho mọi cạnh có ít nhất một đầu mút thuộc tập. Có định lý: phần bù của một tập độc lập cực đại là một phủ đỉnh nhỏ nhất, nên |phủ đỉnh nhỏ nhất| = n - (số độc lập).
Hãy in kích thước phủ đỉnh nhỏ nhất.
Dòng đầu n m. m dòng cạnh vô hướng u v.
1 <= n <= 40; 0 <= m <= n*(n-1)/2.
Một số nguyên: kích thước phủ đỉnh nhỏ nhất.
Ví dụ:
Đầu vào:
5 4
1 2
2 3
3 4
4 5
Đầu ra:
2
Giải thích:
Đang tải editor...