Cod sursa(job #454666)

Utilizator sapiensCernov Vladimir sapiens Data 12 mai 2010 10:41:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.97 kb
Program Dfs;
 type list = ^cell;
      cell = record
               inf:longint;
               next:list;
             end;
 var f,g:text; x,y,i,n,m,k:longint;
     a:array[1..100000,1..2]of list;
     b:array[1..100000]of boolean;
 procedure visit (x:longint);
  begin
   if not b[x] then begin
     b[x]:=true;
     a[x,2]:=a[x,1];
     while a[x,2]^.next<>nil do begin
       a[x,2]:=a[x,2]^.next;
       visit (a[x,2]^.inf);
     end;
   end;
  end;
 begin
  assign (f,'dfs.in'); reset (f);
  assign (g,'dfs.out'); rewrite (g);
  readln (f,n,m);
  for i:=1 to n do begin
    new (a[i,1]);
    a[i,2]:=a[i,1];
  end;
  for i:=1 to m do begin
    readln (f,x,y);
    new (a[x,2]^.next);
    a[x,2]:=a[x,2]^.next;
    a[x,2]^.inf:=y;
    new (a[y,2]^.next);
    a[y,2]:=a[y,2]^.next;
    a[y,2]^.inf:=x;
  end;
  for i:=1 to n do
    if not b[i] then begin
      inc (k);
      visit (i);
    end;
  writeln (g,k);
  close (f); close (g);
 end.