NKBM - Cặp ghép cực đại trên đồ thị hai phía
Tác giả: RR
Ngôn ngữ: Pascal
const
MAXN=1011;
type
list=^node;
node=record
u:longint;
next:list;
end;
procedure add(u:longint; var a:list);
var
p:list;
begin
new(p); p^.u:=u;
p^.next:=a; a:=p;
end;
var
n,m,k,u,v,x,y:longint;
ke:array[1..MAXN] of list;
matchX,matchY,trace,queue:array[1..MAXN] of longint;
function findPath(x:longint):longint;
var
u,v,first,last:longint;
p:list;
begin
fillchar(trace,sizeof(trace),0);
first:=1; last:=1; queue[1]:=x;
while first<=last do
begin
u:=queue[first]; inc(first);
p:=ke[u];
while p<>nil do
begin
v:=p^.u; p:=p^.next;
if (trace[v]=0) and (matchY[v]<>u) then
begin
trace[v]:=u;
if matchY[v]=0 then exit(v);
inc(last); queue[last]:=matchY[v];
end;
end;
end;
exit(0);
end;
procedure enlarge(y:longint);
var
x,next:longint;
begin
while y<>0 do
begin
x:=trace[y];
next:=matchX[x];
matchX[x]:=y;
matchY[y]:=x;
y:=next;
end;
end;
begin
read(n,m,k);
for k:=1 to k do
begin
read(u,v);
add(v,ke[u]);
end;
for x:=1 to n do
begin
y:=findPath(x);
enlarge(y);
end;
y:=0;
for x:=1 to n do
if matchX[x]<>0 then inc(y);
writeln(y);
end.