fork(2) download
copy 
  1. {$M 400000000}
  2. const maxn = 10000;
  3.       fi = '';
  4.       fo = '';
  5.       oo = 60000;
  6. type tqueue = record
  7.                 front,rear,nitem:word;
  8.                 item: array[0..maxn-1] of word;
  9.               end;
  10.      pnode = ^node;
  11.      node = record
  12.               v: word;
  13.               next: pnode;
  14.             end;
  15. var n,m,s:word;
  16.     g: array[1..maxn] of pnode;
  17.     queue: tqueue;
  18.     sen: node;
  19.     nilt: pnode;
  20. procedure insert(u,v:word);
  21. var p:pnode;
  22. begin
  23.   new(p);
  24.   p^.v:=v;
  25.   p^.next:=g[u];
  26.   g[u]:=p;
  27. end;
  28. function found(u,v:word):boolean;
  29. var p:pnode;
  30. begin
  31.   found:=false;
  32.   p:=g[u];
  33.   while p<>nilt do
  34.   begin
  35.     found:=(found or (p^.v=v));
  36.     if found then exit;
  37.     p:=p^.next;
  38.   end;
  39. end;
  40. procedure enter;
  41. var i,j,u,v:word;
  42.     {a: array[1..maxn,1..maxn] of boolean;}
  43. begin
  44.   assign(input,fi);
  45.   reset(input);
  46.   readln(n,m,s);
  47.   {for i:=1 to n do
  48.   for j:=1 to n do
  49.   a[i,j]:=false;}
  50.   sen.v:=0;
  51.   nilt:=@sen;
  52.   for i:=1 to n do
  53.   g[i]:=nilt;
  54.   for i:=1 to m do
  55.   begin
  56.     readln(u,v);
  57.     if not found(u,v) then
  58.     begin
  59.       {a[u,v]:=true;}
  60.       insert(u,v);
  61.     end;
  62.   end;
  63.   close(input);
  64. end;
  65. procedure initq;
  66. begin
  67.   with queue do
  68.   begin
  69.     front:=0;
  70.     rear:=1;
  71.     nitem:=0;
  72.   end;
  73. end;
  74. function empty:boolean;
  75. begin
  76.   with queue do
  77.   empty:=(nitem=0);
  78. end;
  79. procedure push(v:word);
  80. begin
  81.   with queue do
  82.   begin
  83.     front:=(front+1) mod maxn;
  84.     inc(nitem);
  85.     item[front]:=v;
  86.   end;
  87. end;
  88. function pop:word;
  89. begin
  90.   with queue do
  91.   begin
  92.     pop:=item[rear];
  93.     rear:=(rear+1) mod maxn;
  94.     dec(nitem);
  95.   end;
  96. end;
  97. procedure bfs;
  98. var u,v,res,i:word;
  99.     p:pnode;
  100.     d: array[1..maxn] of word;
  101.     sta: array[1..maxn] of boolean;
  102. begin
  103.   initq;
  104.   fillchar(d,sizeof(d),oo);
  105.   fillchar(sta,sizeof(sta),false);
  106.   res:=0;
  107.   push(s);
  108.   d[s]:=0;
  109.   repeat
  110.     u:=pop;
  111.     p:=g[u];
  112.     while p<>nilt do
  113.     begin
  114.       v:=p^.v;
  115.       {writeln(u,' ',v,' ',d[u],' ',d[v]);}
  116.       if d[u]+1<d[v] then
  117.       begin
  118.         d[v]:=d[u]+1;
  119.         push(v);
  120.         if sta[u] then
  121.         begin
  122.           if not sta[v] then
  123.           begin
  124.             sta[v]:=true;
  125.             inc(res);
  126.           end;
  127.         end;
  128.       end
  129.       else
  130.       if d[u]+1=d[v] then
  131.       begin
  132.         if not sta[v] then
  133.         begin
  134.           sta[v]:=true;
  135.           inc(res);
  136.         end;
  137.       end;
  138.       p:=p^.next;
  139.     end;
  140.   until empty;
  141.   {for i:=1 to n do write(d[i],' ');
  142.   writeln;}
  143.   writeln(res);
  144. end;
  145. procedure solve;
  146. var i:word;
  147. begin
  148.   assign(output,fo);
  149.   rewrite(output);
  150.   bfs;
  151.   close(output);
  152. end;
  153. begin
  154.   enter;
  155.   solve;
  156. end.
Success #stdin #stdout 0s 364KB
comments (?)
stdin
copy 
6 11 1
1 5
1 5
5 6
1 2
5 4
2 4
4 3
5 4
5 2
3 2
6 5
stdout
copy 
2
https://ideone.com/ZRCuz7
language:
Pascal (fpc 3.0.4)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!