Cod sursa(job #164435)

Utilizator adalLica Adela adal Data 24 martie 2008 10:56:23
Problema Parcurgere DFS - componente conexe Scor 50
Compilator fpc Status done
Runda Arhiva educationala Marime 1.15 kb
program df;

type point=^lista;
   lista=record
    inf:longint;
    leg:point;
end;

var l:array[0..1000] of point;
    s,nv,t,d:array[0..1000] of longint;
    sel:array[0..1000] of boolean;
    time,nr,m,n,i,j,x,y:longint;
    f,g:text;
    p:point;

procedure df(nod:longint);
var p:point;
begin
    sel[nod]:=true;
    p:=l[nod];    inc(time);
    d[nod]:=time;
    while p <>nil do begin
        if sel[p^.inf]=false then begin
            t[p^.inf]:=nod;
            nv[p^.inf]:=nv[nod]+1;
            df(p^.inf);
        end;
        p:=p^.leg;
    end;
    inc(time); s[nod]:=time;
end;


begin
    assign(f,'dfs.in'); reset(f);
    assign(g,'dfs.out'); rewrite(g);
    readln(f,n,m);
    for i:=1 to n do l[i]:=nil;
    for i:=1 to m do begin
        readln(f,x,y);
        new(p); p^.inf:=x; p^.leg:=l[y]; l[y]:=p;
        new(p); p^.inf:=y; p^.leg:=l[x]; l[x]:=p;
    end;
    fillchar(sel, sizeof(sel), 0);
    nr:=0;
    for i:=1 to n do
        if sel[i]=false then begin inc(nr); df(i); end;
{    for i:=1 to n do writeln(g,nv[i],' ',d[i],' ',s[i],' ',t[i]); }
    writeln(g,nr);

    close(f); close(g);
end.