Cod sursa(job #157749)

Utilizator DonPushmeMilitaru Adrian DonPushme Data 13 martie 2008 11:23:20
Problema Parcurgere DFS - componente conexe Scor 65
Compilator fpc Status done
Runda Arhiva educationala Marime 1.03 kb
type lista=^element;
     element=record
        edge:longint;
        next:lista;
        end;
const inf=maxint;
      nmax=100001;
var list:array[1..nmax] of lista;
    v:array[1..nmax] of integer;
    t,n,m,k:longint;
    p:lista;

procedure citire;
var i,a,b:longint;
begin
assign(input,'dfs.in');reset(input);
readln(n,m);
for i:=1 to m do
        begin
        read(a,b);
        new(p);
        p^.edge:=a;
        p^.next:=list[b];
        list[b]:=p;

        new(p);
        p^.edge:=b;
        p^.next:=list[a];
        list[a]:=p;
        end;
end;

procedure dfs(nod:integer);
var p:lista;
begin
v[nod]:=1;
p:=list[nod];
while p<>nil do
        begin
        if v[p^.edge]=0 then dfs(p^.edge);
        p:=p^.next;
        end;
end;

begin {main}
citire;
fillchar(v,sizeof(v),0);
k:=0;
for t:=1 to n do
        if v[t]=0 then
                begin
                inc(k);
                dfs(t);
                end;
assign(output,'dfs.out');rewrite(output);
write(k);
close(output);
end.