Cod sursa(job #682347)
Utilizator | 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.