fork download
copy 
  1. {$M 400000000}
  2. const maxn = 10000;
  3.       fi = '';
  4.       fo = '';
  5. type tqueue = record
  6.                 front,rear,nitem:word;
  7.                 item: array[0..maxn-1] of word;
  8.               end;
  9. var n,s,t:word;
  10.     m:longint;
  11.     g: array[1..maxn,0..maxn] of word;
  12.     trace: array[1..maxn] of word;
  13.     queue: tqueue;
  14. procedure enter;
  15. var i:longint;
  16.     u,v:word;
  17. begin
  18.   assign(input,fi);
  19.   reset(input);
  20.   readln(n,m,s,t);
  21.   for i:=1 to n do
  22.   g[i,0]:=0;
  23.   for i:=1 to m do
  24.   begin
  25.     readln(u,v);
  26.     inc(g[u,0]);
  27.     g[u,g[u,0]]:=v;
  28.   end;
  29.   close(input);
  30. end;
  31. procedure initq;
  32. begin
  33.   with queue do
  34.   begin
  35.     front:=0;
  36.     rear:=1;
  37.     nitem:=0;
  38.   end;
  39. end;
  40. procedure push(v:word);
  41. begin
  42.   with queue do
  43.   begin
  44.     inc(nitem);
  45.     front:=(front+1) mod maxn;
  46.     item[front]:=v;
  47.   end;
  48. end;
  49. function pop:word;
  50. begin
  51.   with queue do
  52.   begin
  53.     dec(nitem);
  54.     pop:=item[rear];
  55.     rear:=(rear+1) mod maxn;
  56.   end;
  57. end;
  58. function empty:boolean;
  59. begin
  60.   with queue do
  61.   empty:=(nitem=0);
  62. end;
  63. procedure printtrace;
  64. var i:word;
  65. begin
  66.   for i:=1 to n do
  67.   write(trace[i],' ');
  68.   writeln;
  69. end;
  70. procedure bfs;
  71. var i,j:word;
  72.     visit: array[1..maxn] of boolean;
  73. begin
  74.   initq;
  75.   fillchar(visit,sizeof(visit),false);
  76.   fillchar(trace,sizeof(trace),0);
  77.   push(s);
  78.   visit[s]:=true;
  79.   repeat
  80.     i:=pop;
  81.     for j:=1 to g[i,0] do
  82.     if not visit[g[i,j]] then
  83.     begin
  84.       push(g[i,j]);
  85.       visit[g[i,j]]:=true;
  86.       trace[g[i,j]]:=i;
  87.       if g[i,j]=t then exit;
  88.     end;
  89.   until empty;
  90. end;
  91. procedure solve;
  92. var lock,res:word;
  93.     visit: array[1..maxn] of boolean;
  94. function dfs(i:longint):boolean;
  95. var j:longint;
  96.     p:boolean;
  97. begin
  98.   visit[i]:=true;
  99.   if i=t then dfs:=true
  100.   else
  101.   if i=lock then dfs:=false
  102.   else
  103.   begin
  104.     p:=false;
  105.     for j:=1 to g[i,0] do
  106.     if not visit[g[i,j]] then
  107.     begin
  108.       p:=p or dfs(g[i,j]);
  109.       if p then break;
  110.     end;
  111.     dfs:=p;
  112.   end;
  113. end;
  114. begin
  115.   assign(output,fo);
  116.   rewrite(output);
  117.   bfs;
  118.   lock:=trace[t];
  119.   res:=0;
  120.   while (lock<>s) and (lock<>0) do
  121.   begin
  122.     fillchar(visit,sizeof(visit),false);
  123.     if not dfs(s) then inc(res);
  124.     lock:=trace[lock];
  125.   end;
  126.   writeln(res);
  127.   close(output);
  128. end;
  129. begin
  130.   enter;
  131.   solve;
  132. end.
Success #stdin #stdout 0s 195584KB
comments (?)
stdin
copy 
7 10 1 5
1 2
1 3
2 4
3 4
4 5
5 6
6 2
6 7
7 3
7 5
stdout
copy 
1
https://ideone.com/5cW4KF
language:
Pascal (fpc 3.0.4)
created:
9 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!