STABLE - VOI10 - Ổn định

Tác giả: flashmt

Ngôn ngữ: Pascal

const oo=100000000;
var m,n,s,re,num,cr:longint;
    a:array[0..51000] of longint;
    b:array[0..51000,0..1] of longint;
    pos,sl,cur,d,e,q:array[0..10100] of longint;
    free:array[0..10100] of boolean;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
      i:=l; j:=r; x:=b[(i+j) div 2,0]; y:=b[(i+j) div 2,1];
      repeat
            while (b[i,0]<x) or ((b[i,0]=x) and (b[i,1]<y)) do i:=i+1;
            while (b[j,0]>x) or ((b[j,0]=x) and (b[j,1]>y)) do j:=j-1;
            if i<=j then
            begin
                t:=b[i,0]; b[i,0]:=b[j,0]; b[j,0]:=t;
                t:=b[i,1]; b[i,1]:=b[j,1]; b[j,1]:=t;
                i:=i+1; j:=j-1;
            end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
end;

procedure rf;
var i:longint;
begin
    read(n,m,s);
    for i:=1 to m do read(b[i,0],b[i,1]);
    sort(1,m);
    for i:=1 to m do
        if (b[i,0]<>b[i-1,0]) or  (b[i,1]<>b[i-1,1]) then inc(sl[b[i,0]]);
    pos[1]:=1; cur[1]:=1;
    for i:=2 to n+1 do
    begin
         pos[i]:=pos[i-1]+sl[i-1];
         cur[i]:=pos[i];
    end;
    for i:=1 to m do
        if (b[i,0]<>b[i-1,0]) or (b[i,1]<>b[i-1,1]) then
        begin
             a[cur[b[i,0]]]:=b[i,1];
             inc(cur[b[i,0]]);
        end;
end;

procedure init;
var i:longint;
begin
    for i:=1 to n do
    begin
        d[i]:=oo; free[i]:=true; e[i]:=0;
    end;
end;

procedure pr;
var i,x,y:longint;
begin
     init;
     cr:=1; num:=1; q[1]:=s;
     d[s]:=0; e[s]:=1;
     repeat
           x:=q[cr];  free[x]:=false;
           for i:=pos[x] to pos[x+1]-1 do
           begin
                y:=a[i];
                if free[y] then
                begin
                     if d[y]=oo then
                     begin
                          inc(num);
                          q[num]:=y;
                     end;
                     if d[y]=d[x]+1 then e[y]:=2
                     else
                     begin
                          if d[y]>d[x]+1 then
                          begin
                            d[y]:=d[x]+1;
                            e[y]:=e[x];
                          end;
                     end;
                end;
           end;
           inc(cr);
     until cr>num;
     re:=0;
     for i:=1 to n do
         if e[i]>1 then inc(re);
     writeln(re);
end;

begin
     rf;
     pr;
end.

Download