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

Nguồn đề bài cặp ghép không trọng số: http://vn.spoj.com/problems/MATCH1/

1. Đề bài 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

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

2. Code cặp ghép không trọng số Pascal

Đây là code thuật toán cặp ghép thôi. không có hướng dẫn gì cả.

Code mẫu cặp ghép được viết dựa trên Cuốn DSAP của thầy Lê Minh Hoàng, giáo viên khối chuyên Sư Phạm.

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:array[0..nmax+1,0..nmax+1] of byte;
        Q,MatchX,MatchY,tr:array[0..nmax+1] of data;
        n,m,dau,cuoi:data;

procedure docfile;
var     i,j,u,v:data;
begin
        assign(f,fi); reset(f);
        fillchar(a,sizeof(a),0);
        readln(f,m,n);
        while not eof(f) do
                begin
                        readln(f,u,v);
                        a[u,v]:=1;
                end;
        close(f);
end;

procedure them(x:data);
begin
        inc(cuoi);
        q[cuoi]:=x;
end;

function lay:data;
begin
        lay:=q[dau];
        inc(dau);
end;

function BFS:data;
var     i,j,u,v:data;
begin
        dau:=1;
        cuoi:=0;
        fillchar(tr,sizeof(tr),0);
        for i:=1 to m do
                if matchX[i]=0 then
                        them(i);
        while dau<=cuoi do
                begin
                        u:=lay;
                        for v:=1 to n do
                                if (a[u,v]=1) and (tr[v]=0) then
                                        begin
                                                tr[v]:=u;
                                                if matchy[v]=0 then
                                                        exit(v);
                                                them(matchy[v]);
                                        end;
                end;
        exit(0);
end;

procedure enlager(u:data);
var
        v,next:data;
begin
        repeat
                v:=tr[u];
                next:=matchx[v];
                matchx[v]:=u;
                matchy[u]:=v;
                u:=next;
        until u=0;
end;

procedure xuli;
var     i,j,res,d:data;
begin
        fillchar(matchx,sizeof(matchx),0);
        fillchar(matchy,sizeof(matchy),0);
        repeat
                d:=bfs;
                if d<>0 then
                        enlager(d);
        until   d=0;
        res:=0;
        for i:=1 to m do
                if matchx[i] <>0 then
                        inc(res);
        writeln(res);
        for i:=1 to m do
                if matchx[i]<>0 then
                        writeln(i,' ',matchx[i]);
end;

begin
        docfile;
        xuli;
end.