Cod sursa(job #701321)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 1 martie 2012 15:13:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.75 kb
type muchie=^nod;
     nod=record n:longint; a:muchie; end;

var v:array [1..100000] of muchie;
    chk:array [1..100000] of boolean;
    i, n, m, t, x, y:longint;
    p:muchie;
    f, g:text;

procedure dfs(fx:longint);
var q:muchie;
  begin
  q:=v[fx];
  chk[fx]:=true;

  while q<> nil do
    begin
    if chk[q^.n]=false then dfs (q^.n);
    q:=q^.a;
    end;
  end;

begin
assign (f, 'dfs.in'); reset (f);
assign (g, 'dfs.out'); rewrite (g);

read (f, n, m);
for i := 1 to m do
  begin
  read (f, x, y);
  new (p); p^.n:=y; p^.a:=v[x]; v[x]:=p;
  new (p); p^.n:=x; p^.a:=v[y]; v[y]:=p;
  end;

for i := 1 to n do
  begin
  if chk[i]=false then begin inc (t); dfs(i); end;
  end;

writeln (g, t);
close (f); close (g);

end.