GRAPH_ - Tìm khớp và cầu (Cơ bản)

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
var n,m,i,j,cnt,cau,khop:longint;
    p,low,num,cha,con:array[1..10010] of longint;
    a,b,c:array[1..100010] of longint;
    d:array[1..10010] of boolean;

procedure visit(x,y:longint);
var i:longint;
begin
     inc(cnt); num[x]:=cnt; low[x]:=cnt;
     cha[x]:=y;
     for i:=p[x]+1 to p[x+1] do
         if a[i]<>y then
         begin
              if num[a[i]]>0 then low[x]:=min(low[x],num[a[i]])
              else
              begin
                   visit(a[i],x);
                   low[x]:=min(low[x],low[a[i]]);
              end;
         end;
end;

begin
     read(n,m);
     for i:=1 to m do
     begin
          read(b[i],c[i]);
          inc(p[b[i]]);
          inc(p[c[i]]);
     end;
     for i:=2 to n+1 do inc(p[i],p[i-1]);
     for i:=1 to m do
     begin
          a[p[b[i]]]:=c[i];
          dec(p[b[i]]);
          a[p[c[i]]]:=b[i];
          dec(p[c[i]]);
     end;
     for i:=1 to n do
         if cha[i]=0 then visit(i,-1);
     for i:=1 to n do
         if cha[i]>0 then inc(con[cha[i]]);
     for i:=1 to n do
     begin
          j:=cha[i];
          if j<0 then continue;
          if low[i]>=num[i] then inc(cau);
          if d[j] then continue;
          if (low[i]>=num[j]) and ((cha[j]<>-1) or (con[j]>1)) then
          begin
               d[j]:=true; inc(khop);
          end;
     end;
     writeln(khop,' ',cau);
end.

Download