Cod sursa(job #715128)

Utilizator Buzu_Tudor_RoCont vechi Buzu_Tudor_Ro Data 16 martie 2012 18:32:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.14 kb
Program p1;
type lista=^celula;
     celula=record
            info:longint;
            next:lista;
            end;

var fi,fo :text;
    l : array[0..100001] of lista;
    b : array[0..100001] of integer;
    v : lista;
    i,n,m,q,x,y : longint;

procedure dfs_t(k:longint);
var r:lista;
begin
    r:=l[k]; b[k]:=1;
    while r<>nil do begin
                    if b[r^.info]=0 then dfs_t(r^.info);
                    r:=r^.next;
                    end;
end;

begin
    assign(fi,'dfs.in'); reset(fi); readln(fi,n,m);
    assign(fo,'dfs.out'); rewrite(fo);
    for i:=1 to n do begin
                     l[i]:=nil;
                     b[i]:=0;
                     end;
    for i:=1 to m do begin
                     readln(fi,x,y);
                     new(v);
                     v^.info:=y; v^.next:=l[x]; l[x]:=v;
                     new(v);
                     v^.info:=x; v^.next:=l[y]; l[y]:=v;
                     end;

    for i:=1 to n do
      if b[i]=0 then begin
                     q:=q+1;
                     dfs_t(i);
                     end;
    write(fo,q);
    close(fi); close(fo);
end.