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

Tác giả: flashmt

Ngôn ngữ: Pascal

var n,m,x,y,re,nq,i:longint;
    c,f:array[1..111,1..111] of longint;
    a,b,d,q:array[1..111] of longint;

function find(var u:longint):boolean;
var i:longint;
begin
     fillchar(d,sizeof(d),0);
     nq:=0;
     for i:=1 to m do
         if a[i]=0 then
         begin
              inc(nq);
              q[nq]:=i;
         end;
     i:=1;
     while i<=nq do
     begin
          x:=q[i]; inc(i);
          for y:=1 to n do
              if (d[y]=0) and (c[x][y]=1) then
              begin
                   d[y]:=x;
                   if b[y]=0 then
                   begin
                        u:=y; exit(true);
                   end;
                   inc(nq);
                   q[nq]:=b[y];
              end;
     end;
     find:=false;
end;

procedure incflow(y:longint);
var x,t:longint;
begin
     while y>0 do
     begin
          x:=d[y]; t:=y; y:=a[x];
          b[t]:=x; a[x]:=t;
     end;
end;

begin
     read(m,n);
     while not eof do
     begin
          read(x);
          if x<=0 then break;
          read(y);
          c[x][y]:=1;
     end;
     while find(i) do incflow(i);
     for i:=1 to m do
         if a[i]>0 then inc(re);
     writeln(re);
     for i:=1 to m do
         if a[i]>0 then writeln(i,' ',a[i]);
end.

Download