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.|

MATCH1 - Cặp ghép không trọng số

Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xm, các đỉnh của Y ký hiệu là y1, y2, ..., yn.
Một bộ ghép trên G là một tập các cạnh thuộc E đôi một không có đỉnh chung.

Yêu cầu: Hãy tìm bộ ghép cực đại (có nhiều cạnh nhất) trên G.

Chú ý : Dùng Eof chứ không dùng SeekEof.

Input

• Dòng 1: Chứa hai số m, n (1 ≤ m, n ≤ 100)
• Các dòng tiếp, mỗi dòng chứa hai số nguyên dương i, j cho biết thông tin về một cạnh (xi, yj) thuộc E.

Output

• Dòng 1: Ghi số cạnh trong bộ ghép cực đại tìm được (K).
• K dòng tiếp theo, mỗi dòng ghi thông tin về một cạnh được chọn vào bộ ghép cực đại: Gồm 2 số u, v thể hiện cho cạnh nối (xu, yv).

Example

match1.gif
Input:
4 5
1 1
1 4
2 1
2 2
2 4
3 2
3 3
4 2
4 3


Output:
4
1 1
2 4
3 3
4 2


Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-25
Thời gian chạy:0.209s
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 NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Cuốn DSAP của thầy Lê Minh Hoàng, giáo viên khối chuyên Sư Phạm

hide comments
2017-12-22 04:15:36
kham khảo code:
https://vietcodes.github.io/code/126/
2017-12-05 09:18:57
làm bài nay hay hơn. Do có nhiều cách ghép ra nghiệm là 4 mà .
http://vn.spoj.com/problems/NKBM/
2017-08-20 19:03:45 Con Bò Huyền Thoại
https://kienthuc24h.com/match1-spoj-cap-ghep-khong-trong-so/
2016-11-16 09:25:03 Ðoàn Vãn Thanh An


Last edit: 2016-11-16 09:25:12
2016-09-27 11:11:39 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/149/match1-spoj/
2014-08-14 11:04:32 Thcs Ðặng Chánh Kỷ
hoc va ac ngay tren lop
2012-02-05 09:41:18 maradona
dung seekeof, van ACC ma!
2010-12-29 12:47:12 KO
Bài này có nhiều Kq khác nhau
2009-03-04 02:00:48 Hy Trường Sơn
cac anh cho em hoi cach input bai nay cai
sao em dung while not eof(f) do
begin
readln(f,u,v);
C[u,v]:=true;
end;
khong duoc
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.