Cod sursa(job #1345577)

Utilizator mihai1996Toader Mihai mihai1996 Data 17 februarie 2015 18:56:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.81 kb
program dfs_2;
var f,g:text;
    start,viz:array[1..100000] of longint;
    t:array[0..1,1..400000] of longint;
    i,j,n,m,x,y,nr,k:longint;

procedure df(nod:longint);
var p:longint;
begin
  viz[nod]:=1;
  p:=start[nod];
  while p<>0 do
    begin
      if viz[t[0,p]]=0 then
        df(t[0,p]);
      p:=t[1,p];
    end;
end;

begin
  assign(f,'dfs.in'); reset(f);
  assign(g,'dfs.out'); rewrite(g);
  readln(f,n,m);
  k:=0;
  for i:=1 to m do
    begin
      readln(f,x,y);
      inc(k);
      t[0,k]:=y;
      t[1,k]:=start[x];
      start[x]:=k;
      inc(k);
      t[0,k]:=x;
      t[1,k]:=start[y];
      start[y]:=k;
    end;
  nr:=0;
  for i:=1 to n do
    if viz[i]=0 then
      begin
        inc(nr);
        df(i);
      end;
  writeln(g,nr);
  close(f); close(g);
end.