Реализация поиска максимального паросочетения

{
  edge(i,j) — матрица смежности
  Пусть она дана.
}

const
  max = 100;

var
  v: array[1..max] of boolean;
  goes: array[1..max] of integer;

function dfs(j: Integer): boolean;
var
  i: Integer;
begin
  if v[j] then begin
    dfs := false;
    exit;
  end;
  v[j] := true;
  for i := 1 to n do
    if edge(j, i) and ((goes[i] = 0) or dfs(goes[i])) then begin
      dfs := true;
      goes[i] := j;
      exit;
    end;
  dfs := false;
end;

function maxpares: Integer;
var cnt: Integer;
begin
  fillchar(goes, sizeof(goes), 0);
  cnt := 0;
  for j := 1 to m do begin
    fillchar(v, sizeof(v), false);
    if dfs(j) then
      inc(cnt);
  end;
  maxpares := cnt;
end

{ (C) Igor Kvasov }
const
  maxn = 2000;
var
  n,m,r,i,j,u,v,ans:longint;
  ne,use,was:array[1..maxn]of longint;
  e,p:array[1..maxn,1..maxn] of integer;
  ok,ok0:boolean;

procedure find(u:longint);
var
  i:longint;
begin
  if was[u]=1 then exit;
  if (u>n)and(use[u]=0) then begin
    use[u]:=1; ok:=true; exit;
  end;
  was[u]:=1;
  for i:=1 to ne[u] do if (u<=n)xor(p[u,e[u,i]]=1) then begin
    find(e[u,i]);
    if ok then begin
      p[u,e[u,i]]:=1-p[u,e[u,i]];
      p[e[u,i],u]:=1-p[e[u,i],u];
      use[u]:=1;
      exit;
    end;
  end;
end;

begin
  read(n,m,r);
  for i:=1 to r do begin
    read(u,v);
    inc(ne[u]); e[u,ne[u]]:=n+v;
    inc(ne[n+v]); e[n+v,ne[n+v]]:=u;
  end;
  for i:=1 to n do begin
    fillchar(was,sizeof(was[1])*(n+m),0);
    if use[i]=0 then begin ok:=false;find(i);end;
  end;
  for i:=1 to n do inc(ans,use[i]);
  writeln(ans);
  for i:=1 to n do if use[i]=1 then begin
    write(i,' ');
    for j:=1 to ne[i] do if p[i,e[i,j]]=1 then begin writeln(e[i,j]-n);break;end;
  end;
end.

#include <cstdio>
#include <vector>
#define MAX 10001
using namespace std;

vector<int> G2B( MAX, 0 );       // G2B[g] — мальчик, который назначен девочке "g"
vector< vector<int> > W( MAX );  // W[b] — список смежных девочек мальчика "b"

int k; // мальчик, начиная с которого мы ищем улучшающий путь
       // и одновременно цвет, в который мы закрашиваем всех мальчиков, до которых
       // мы можем добраться из мальчика k.

vector<int> V(MAX, 0); // цвета вершин-мальчиков

int dfs( int b ) {
    if( V[b] != k ) {
       V[b] = k;
       for( int j = 0; j < W[b].size(); j++ ) {
            if( G2B[ W[b][j] ] == 0 || dfs( G2B[ W[b][j] ] ) ) {
                G2B[ W[b][j] ] = b;
                return 1;
            }
       }
    }
    return 0;
}

int main() {
    int Ng, Nb;     // число девочек и число мальчиков
    int E;          // число рёбер
    int g, b, res;
    scanf("%d%d%d", &Ng, &Nb, &E);
    while(E--) {
       scanf("%d%d", &g, &b); // девочка "g" соединена ребром с мальчиком "b"
       W[b].push_back(g);
    }
   for(k = 1, res = 0; k <= Nb; k++) {
      res += dfs(k);//пытаемся найти пару каждому из мальчиков
   }
    printf( "%d\n", res );
    for(g = 1; g <= Ng; g++)
       if( G2B[g] != 0 )
            printf("%d %d\n", g, G2B[g]);
    return 0;
}