MATCH1 – SPOJ

Đề bài: http://vn.spoj.com/problems/MATCH1/

Thuật toán:

• Đây là bài sử dụng thuật toán cặp ghép cơ bản
• Bạn có thể tham khảo tài liệu về thuật toán cặp ghép tại: http://yeulaptrinh.de/150/tong-hop-tai-lieu-ve-thuat-toan-cap-ghep/

Code:

const
  fi='';
  fo='';
  maxn=100;
var
  a : array[1..maxn,1..maxn] of boolean;
  match : array[1..maxn] of longint;
  i,j,n,m,res : longint;
procedure enter;
  var u,v : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    while not eof(input) do
      begin
        readln(u,v);
        a[u,v] := true;
      end;
  end;
procedure process;
  var found : boolean;
      nlist,i,j,old : longint;
      list : array[1..maxn] of longint;
      cx : array[1..maxn] of boolean;
  procedure dfs(u : longint);
    var i,v : longint;
    begin
      for v:=1 to m do
        if a[u,v] then
          if cx[v] then
          begin
            cx[v] := false;
            if match[v]=0 then found := true else dfs(match[v]);
            if found then
              begin
                match[v] := u;
                exit;
              end;
          end;
    end;
  begin
    nlist := n;
    for i:=1 to n do list[i ] := i;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until old = nlist;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    for i:=1 to m do if match[i]<>0 then inc(res);
    writeln(res);
    for i:=1 to m do if match[i]<>0 then writeln(match[i],' ',i);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.