Cod sursa(job #253626)

Utilizator TudorutzuMusoiu Tudor Tudorutzu Data 6 februarie 2009 00:52:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.31 kb
type point=^nod;
     nod=record
     inf:longint;
     leg:point;
     end;
var t:array[1..100000] of integer;
    n,m,nr,i:longint;
    c:array[1..1000000] of longint;
    a:array[1..100000] of point;
    sel:array[1..100000] of boolean;
    f,g:text;
procedure load;
var p:point;
    i,x,y:longint;
begin
     assign(f,'dfs.in'); reset(f);
     assign(g,'dfs.out'); rewrite(g);
     readln(f,n,m);
     fillchar(t,sizeof(t),0);
     for i:=1 to n do a[i]:=nil;
     fillchar(sel,sizeof(sel),false);
     for i:=1 to m do
     begin
          readln(f,x,y);
          if x<>y then begin
           new(p);
           p^.inf:=y;
           p^.leg:=a[x];
           a[x]:=p;
           new(p);
           p^.inf:=x;
           p^.leg:=a[y];
           a[y]:=p;
          end;
     end;
end;
procedure df(x:longint);
begin
     sel[x]:=true;
     while a[x]<>nil do
     begin
          if sel[a[x]^.inf]=false then
          begin
               t[a[x]^.inf]:=t[x];
               df(a[x]^.inf);
          end;
          a[x]:=a[x]^.leg;
     end;
end;
begin
     load;
     nr:=0;
     for i:=1 to n do
          if sel[i]=false then
          begin
               inc(nr);
               t[i]:=nr;
               df(i);
          end;
     writeln(g,nr);
     close(g);
end.