Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKBAS - Trung tâm bảo hành

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkbas


Một công ty máy tính bán hàng cho các khách hàng ở N thành phố (3 ≤ N ≤ 35) đánh số từ 1 đến N. Có M đoạn đường, mỗi đoạn đường nối hai thành phố nào đó. Công ty muốn mở các trung tâm bảo hành đặt tại một số thành phố này sao cho mỗi thành phố hoặc là có trung tâm bảo hành đặt tại nó hoặc có trung tâm bảo hành đặt ở thành phố có đoạn đường nối trực tiếp với nó.

Yêu cầu: Hãy xác định xem công ty cần mở ít nhất bao nhiêu trung tâm để đáp ứng điều kiện trên.

Dữ liệu

  • Dòng đầu tiên chứa hai số N, M cách nhau bởi dấu cách.
  • Mỗi dòng trong số M dòng tiếp theo chứa hai số nguyên là các chỉ số của các đầu mút của một trong số M đoạn đường.

Kết qủa

Ghi ra số lượng trung tâm bảo hành ít nhất cần mở.

Hạn chế

  • Có 40% số test có 3 ≤ N ≤ 15.

Ví dụ

Dữ liệu:
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8

Kết qủa
2

Được gửi lên bởi:Jimmy
Ngày:2008-01-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:VM10 (Luyện tập) - Nguồn: Bulgarian OI 99

hide comments
2021-01-05 17:58:05
oops
2019-03-01 10:26:12
Good problem! %%$
2018-06-01 14:02:49
bài này làm sao để ac vậy mn? mình làm đến 60đ thôi
2016-10-29 15:08:55
dsu
2016-10-12 19:34:21
ngồi 4 tiếng 40đ đề bài như cái đb ( đầu bài )
2016-03-21 03:28:10
.

Last edit: 2016-03-21 04:11:54
2016-03-20 17:59:33
test 1 là test đầu tiên sai và bạn dc 20 điểm :v

2016-03-20 17:55:39
"20 WA-test-1" là lỗi gì ạ
2013-06-03 03:32:15 Ðặng Duy Thảo
cho mình hỏi 60 WA-test-1 là gì vậy, nộp bài xong nó báo cái này mà không hiểu lắm
2012-09-19 09:33:57 ان منتدى
cai na`y 2 chie`u
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.