Một tập độc lập là tập đỉnh đôi một không kề nhau. Số độc lập (independence number) là kích thước tập độc lập lớn nhất. Bài toán NP-khó; với n nhỏ ta giải bằng nhánh-cận trên bitmask (chọn/không chọn một đỉnh, cắt tỉa theo số ứng viên còn lại).
Hãy in số độc lập của đồ thị.
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: số độc lập.
Ví dụ:
Đầu vào:
5 4
1 2
2 3
3 4
4 5
Đầu ra:
3
Giải thích:
Đang tải editor...