Cod sursa(job #682347)

Utilizator lorundlorund lorund Data 18 februarie 2012 21:38:03
Problema Parcurgere DFS - componente conexe Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 2.12 kb
type pnod=^nod;
     nod=record i : longint;
                next : pnod;
                end;
     tip1=record p,u : pnod;
                 end;
var tin,tout : text;
    n,m,x,y,i,c : longint;
    list : array[1..100000]of tip1;
    viz : array[1..100000]of boolean;
    p,u,q,w : pnod;

procedure citad(var qw : tip1; v : longint);
begin
if qw.p=nil then begin new(p);
                       p^.next:=nil;
                       p^.i:=v;
                       qw.p:=p;
                       qw.u:=p;
                       end
            else begin new(p);
                       p^.next:=nil;
                       p^.i:=v;
                       qw.u^.next:=p;
                       qw.u:=p;
                       end;
end;

procedure bf(i : longint);
begin
viz[i]:=true;
new(p);
p^.i:=i;
p^.next:=nil;
u:=p;
while p<>nil do begin w:=list[p^.i].p;
                      while w<>nil do begin if not(viz[w^.i])then begin new(q);
                                                                        q^.i:=w^.i;
                                                                        q^.next:=nil;
                                                                        u^.next:=nil;
                                                                        u:=q;
                                                                        viz[w^.i]:=true;
                                                                        end;
                                            w:=w^.next;
                                            end;
                      q:=p;
                      p:=p^.next;
                      dispose(q);
                      end;
end;

begin
assign(tin,'dfs.in');reset(tin);
readln(tin,n,m);
for m:=1 to m do begin readln(tin,x,y);
                       citad(list[x],y);
                       citad(list[y],x);
                       end;
close(tin);
for i:=1 to n do if not(viz[i])then begin bf(i);
                                          inc(c);
                                          end;
assign(tout,'dfs.out');rewrite(tout);
writeln(tout,c);
close(tout);
end.