fork download 
  1. program connessioni; 
  2. const MAXN =200000;
  3.       Qsize=400000;
  4. var
  5.    N, Q, ricorda, conta,contazone,a ,b, h,i, j, w, z,x, y, risul: longint;
  6.    graph : array[0..MAXN-1] of array of longint;
  7.    gsize, gcapa: array[0..MAXN-1] of longint;
  8.    visited : array[0..MAXN-1] of boolean;
  9.    S,E,dist : array[0..MAXN-1] of longint;
  10.    q1, q2 : array[0..QSIZE-1] of longint;
  11.    uscita: boolean;
  12.  
  13. procedure bfs(b : longint; var res : array of longint);
  14.  var qhead, qcount, first, second, j : longint;
  15.  
  16.  begin
  17.    q1[0] := b; q2[0] := 0;
  18.    qhead := 0; qcount := 1;
  19.    while qcount > 0 do
  20.        begin
  21.          first := q1[qhead];
  22.          second := q2[qhead];
  23.          inc(qhead);
  24.          if qhead = QSIZE then
  25.          qhead := 0;
  26.          dec(qcount);
  27.          if visited[first] then
  28.          continue;
  29.          visited[first] := True; ricorda:=first;
  30.          conta:=conta+1; (*memorizza il numero di nodi visitati*)
  31.          res[first] := second;
  32.          for j:=0 to gsize[first]-1 do
  33.                  begin
  34.                  q1[(qhead + qcount) mod QSIZE] := graph[first][j];
  35.                  q2[(qhead + qcount) mod QSIZE] := second + 1;
  36.                  inc(qcount);
  37.                 end;
  38.        end;
  39.  end;
  40.  
  41. procedure inizia (N: longint);
  42. begin
  43.  for h:=0 to N-1 do
  44.              begin
  45.                setlength(graph[h], 1);
  46.                 (* all’inizio, la lista di adiacenza del nodo i ha dimensione 0
  47.                   * e capacita’ 1. *)
  48.                 gsize[h] := 0;
  49.      gcapa[h] := 1;
  50.      dist[h] := maxlongint;
  51.   end;
  52. end;  
  53.  
  54. function collega (x,y:longint):longint;
  55. begin
  56.   S[i]:=x; E[i]:=y;
  57.        j:=1;
  58.        while j<=Q do 
  59.          begin
  60.           for h:=0 to N-1 do visited[h]:=false;
  61.           inizia(N);
  62.           for h:=0 to j-1 do
  63.              begin
  64.                a := S[h]; b :=E[h];
  65.               (* se ho esaurito i posti nella lista di adiacenza del nodo a *)
  66.               if gsize[a] = gcapa[a] then
  67.                       begin
  68.                         (* allora raddoppio la sua capacita’ *)
  69.                         gcapa[a] := gcapa[a] shl 1;
  70.                         setlength(graph[a], gcapa[a]);
  71.                      end;
  72.               graph[a][gsize[a]] := b;
  73.               inc(gsize[a]);
  74.               (* se ho esaurito i posti nella lista di adiacenza del nodo b *)
  75.               if gsize[b] = gcapa[b] then
  76.                    begin
  77.                     (* allora raddoppio la sua capacita’ *)
  78.                     gcapa[b] := gcapa[b] shl 1;
  79.                     setlength(graph[b], gcapa[b]);
  80.                    end;
  81.               graph[b][gsize[b]] :=a;
  82.               inc(gsize[b]);
  83.            end;
  84.         contazone:=1; conta:=0; 
  85.         bfs(0,dist);
  86.         while conta<N do
  87.                     begin 
  88.                         w:=0; uscita:=false;
  89.                         contazone:=contazone+1;
  90.                         while (uscita=false) and (w<N) do  if visited[w]=true then w:=w+1
  91.                                                                               else begin  uscita:=true;ricorda:=w; end;
  92.                         bfs(ricorda,dist);
  93.                     end; 
  94.         collega:=contazone; j:=j+1; end; 
  95.  end;
  96.  
  97. begin
  98.    (*assign(input, 'input.txt'); reset(input);
  99.    assign(output, 'output.txt'); rewrite(output);*)
  100.    readln(N, Q);
  101.    inizia(N);
  102.    for i:=0 to Q-1 do 
  103.       begin 
  104.        readln (x,y);
  105.        writeln (collega(x,y));
  106.       end;
  107. end.
  108.  
Success #stdin #stdout 0.01s 6448KB
comments (?)
stdin 
10 15
7 9
3 2
7 9
4 0
7 9
5 1
0 4
6 2
6 3
7 9
8 4
1 5
8 9
6 8
9 0
stdout 
9
8
8
7
7
6
6
5
5
5
4
4
3
2
2
https://ideone.com/wvrmAe
language:
Pascal (fpc 3.0.4)
created:
3 days ago
visibility:
public

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!