150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 9 pptx

147

137. PHỦ

Cho một đồ thị vô hướng G = (V, E) có n đỉnh và m cạnh, không có đỉnh cô lập

Hãy chọn ra một tập ít nhất các cạnh để tất cả các đỉnh của đồ thị đều là đầu mút của ít nhất

một cạnh trong tập đã chọn !

Dữ liệu: Vào từ file văn bản COVER.INP

• Dòng 1: Chứa hai số n, m là số đỉnh và số cạnh của đồ thị (1 ≤ n ≤ 100)

• m dòng tiếp theo, mỗi dòng ghi hai số u, v tương ứng với một cạnh (u, v) của đồ thị

Kết quả: Ghi ra file văn bản COVER.OUT

• Dòng 1: Ghi số k là số cạnh được chọn

• k dòng tiếp theo, mỗi dòng ghi chỉ số hai đỉnh đầu mút của một cạnh được chọn

Chú thích nho nhỏ : Bài này sử dụng kiến thức không phổ biến ! Bởi vậy không có gì là khó

hiểu nếu như bạn không làm được !

Ví dụ:

COVER.INP COVER.OUT

10 11

1 2

6 1

2 4

2 8

3 4

3 6

5 6

5 9

5 10

7 8

9 7

5

6 1

2 8

3 4

5 10

9 7