fork download
copy 
  1. program oli3_riconnessioneconbfs; (* ricerca del numero di componenti connessi su  grafo semplice risolto con lista                                di adiacenza e bfs*)
  2. const MAXN =100000;
  3.       Qsize=200000;
  4. var
  5.    N, M, ricorda, conta,contacomponenti,a ,b, h: 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.  
  42. begin
  43.    (*assign(input, 'input.txt'); reset(input);
  44.    assign(output, 'output.txt'); rewrite(output);*)
  45.    readln(N, M);
  46.    for h:=0 to M-1 do readln (S[h],E[h]);
  47.    for h:=0 to N-1 do visited[h]:=false;
  48.     for h:=0 to N-1 do
  49.    begin
  50.      setlength(graph[h], 1);
  51.      (* all’inizio, la lista di adiacenza del nodo i ha dimensione 0
  52.        * e capacita’ 1.
  53.      *)
  54.      gsize[h] := 0;
  55.      gcapa[h] := 1;
  56.      dist[h] := maxlongint;
  57.   end;
  58.  for h:=0 to M-1 do
  59.       begin
  60.        a := S[h]; b := E[h];
  61.        (* se ho esaurito i posti nella lista di adiacenza del nodo a *)
  62.        if gsize[a] = gcapa[a] then
  63.             begin
  64.               (* allora raddoppio la sua capacita’ *)
  65.               gcapa[a] := gcapa[a] shl 1;
  66.               setlength(graph[a], gcapa[a]);
  67.             end;
  68.        graph[a][gsize[a]] := b;
  69.        inc(gsize[a]);
  70.        (* se ho esaurito i posti nella lista di adiacenza del nodo b *)
  71.        if gsize[b] = gcapa[b] then
  72.             begin
  73.               (* allora raddoppio la sua capacita’ *)
  74.               gcapa[b] := gcapa[b] shl 1;
  75.               setlength(graph[b], gcapa[b]);
  76.             end;
  77.        graph[b][gsize[b]] :=a;
  78.        inc(gsize[b]);
  79.     end;
  80.    contacomponenti:=1; conta:=0; 
  81.    bfs(0,dist);
  82.    while conta<N do
  83.                     begin 
  84.                         h:=0; uscita:=false;
  85.                         contacomponenti:=N-contacomponenti+1;
  86.                         while (uscita=false) and (h<N) do  if visited[h]=true then h:=h+1
  87.                                                                              else begin  uscita:=true;ricorda:=h; end;
  88.  
  89.                         bfs(ricorda,dist);
  90.  
  91.               end; 
  92.   writeln (contacomponenti-1);
  93. end.
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4 5
0 2
1 3
3 1
1 2
2 3
stdout
copy 
0
https://ideone.com/zdIva7
language:
Pascal (fpc 3.0.4)
created:
4 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!