Cod sursa(job #654700)
Utilizator | Data | 30 decembrie 2011 19:55:12 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | fpc | Status | done |
Runda | Arhiva educationala | Marime | 2.11 kb |
program kk;
type ref=^inr;
inr=record
a:longint;
adr:ref;
end;
var f:text;
v,u:array[1..100000] of ref;
viz:array[1..100000] of 0..1;
coco,i,n,m,pc,uc,x,y:longint;
c:ref;
cod:array[1..100000] of longint;
begin
assign(f,'dfs.in');
reset(f);
readln(f,n,m);
for i:=1 to m do
begin
readln(f,x,y);
if v[x]=nil then begin
new(c);
v[x]:=c;
c^.a:=y;
c^.adr:=nil;
u[x]:=c;
end
else begin
new(c);
c^.a:=y;
c^.adr:=nil;
u[x]^.adr:=c;
u[x]:=c;
end;
if v[y]=nil then begin
new(c);
v[y]:=c;
c^.a:=x;
c^.adr:=nil;
u[y]:=c;
end
else begin
new(c);
c^.a:=x;
c^.adr:=nil;
u[y]^.adr:=c;
u[y]:=c;
end;
end;
coco:=0;
for i:=1 to n do
if viz[i]=0 then
begin
coco:=coco+1;
pc:=i;
uc:=i;
cod[pc]:=i;
viz[i]:=1;
while pc<=uc do
begin
c:=v[cod[pc]];
while c<>nil do begin
if viz[c^.a]=0 then begin
viz[c^.a]:=1;
uc:=uc+1;
cod[uc]:=c^.a;
end;
c:=c^.adr;
end;
pc:=pc+1;
end;
end;
close(f);
assign(f,'dfs.out');
rewrite(f);
write(f,coco);
close(f);
end.