Теоретический материал

Поиск максимального паросочетания в двудольном графе

Граф называют двудольным, если множество его вершин можно разбить на 2 непересекающихся множества (каждая вершина должна обязательно войти в одно из этих множеств), причем каждое ребро графа начинается в первом из этих множеств, а заканчивается в другом. Максимальное паросочетание — это максимально возможное количество ребер, не имеющих общих концов.

В основной программе каждой вершине одного из множеств мы пытаемся найти допустимую пару (очевидно, что если каждой вершине пара будет найдена, то максимальное паросочетание построено). Делается это с помощью функции dfs. Если для вершины j свободной пары в противоположном множестве нет, то делается попытка построить чередующуюся цепочку, начинающуюся с j-й вершины.

const max=…{размер большего из двух множеств}

var new: array[1..max] of boolean;{смысл противоположен названию!!!}

  res: array[1..max] of integer;

  n, m, i, j, cnt: integer;

function dfs(j: integer): boolean;

{пытается найти вершине j пару}

var i: integer;

begin

  if new[j] then {j в текущем паросочетании уже просмотрена}

    begin dfs:= false; exit end;

  new[j]:= true;

  for i:= 1 to n do

    if a(i, j) {ребро между i и j существует} and

     ((res[i] = 0) {у i еще нет пары}

      or{пару i можно пристроить к другой вершине} dfs(res[i])) then

        begin

          dfs:=true; res[i]:=j; exit

        end;

  dfs:=false

end;

begin {Main}

 …{здесь вводим описание графа}

  fillchar(res,sizeof(res),0);

  cnt:=0;{счетчик ребер в паросочетании}

  for j:= 1 to m do

  {каждой вершине одного из множеств пытаемся найти пару}

    begin

      fillchar(new,sizeof(new),false);

      if dfs(j) then inc(cnt)

    end;

  writeln(cnt);

  for i:= 1 to n do

    if res[i] <> 0 then write(i,' ',res[i])

end.