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

Thuật toán: Đây là bài tập cơ bản về thuật toán tìm cầu, khớp. Bạn có thể tham khảo thuật toán trong ebook Giải thuật và lập trình của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=10000;
  maxm=50000;
  oo=trunc(1e9);
var
  link,head,ke : array[-maxm..maxm] of longint;
  i,j,n,m,kq1,kq2 : longint;
  cau,khop : longint;
  iscut : array[1..maxn] of boolean;
  count : longint;
  cha,num,low : array[1..maxn] of longint;
  free : array[-maxm..maxm] of boolean;
  nchild : array[1..maxn] of longint;
procedure add(i,u,v:longint);
begin
    link[i] :=head[u];
    head[u] := i;
    ke[i]:=v;
end;
procedure enter;
var u,v : longint;
begin
   assign(input,fi);reset(input);
   readln(n,m);
   for i:=1 to m do
     begin
         read(u,v);
         add(i,u,v);
         add(-i,v,u);
     end;
   close(input);
end;
procedure dfs(u:longint);
var i,j,v : longint;
begin
   inc(count);
   num[u]:=count;
   low[u]:=oo;
   i := head[u];
   while i<>0 do
     begin
         if free[i] then
         begin
         v := ke[i];
         free[-i] := false;
         if cha[v]=0 then
           begin
               cha[v]:=u;
               dfs(v);
               low[u] := min(low[v],low[u]);
           end
           else
           begin
               low[u] := min(low[u],num[v]);
           end;
         end;
         i := link[i];
     end;
end;
procedure process;
var i,u,v : longint;
begin
    fillchar(free,sizeof(free),true);
    fillchar(cha,sizeof(cha),0);
    for i:=1 to n do
        if cha[i]=0 then
          begin
              cha[i] := -1;
              dfs(i);
          end;
    for v:=1 to n do
      begin
          u:=cha[v];
          if (u<>-1) and (low[v]>=num[v]) then
                begin
                    inc(cau);
                end;
      end;
    for v:=1 to n do
      if cha[v]<>-1 then
        begin
          inc(nchild[cha[v]]);
        end;
    fillchar(iscut,sizeof(iscut),false);
    for v:=1 to n do
        if cha[v] <> -1 then
        begin
          u := cha[v];
          if low[v]>=num[u] then
            iscut[u]:= iscut[u] or (cha[u]<>-1) or (nchild[u]>=2);
        end;
    for v:=1 to n do
      if iscut[v] then inc(khop);
end;
procedure print;
begin
    assign(output,fo);rewrite(output);
    writeln(khop,' ',cau);
    close(output);
end;
begin
    enter;
    process;
    print;
end.