Pagini recente » Cod sursa (job #3253972) | Cod sursa (job #678570) | Cod sursa (job #2438721) | Cod sursa (job #2384058) | Cod sursa (job #379174)
Cod sursa(job #379174)
{componente conexe cu DF}
type ref=^nod;
nod=record
vf:longint;
leg:ref;
end;
domeniu=0..1;
var sel:array[1..100000] of domeniu;
prim:array[1..100000] of ref;
n,m,nr:longint;
procedure adaug(x,y:longint);
var c:ref;
begin
new(c);
c^.vf:=y;
c^.leg:=prim[x];
prim[x]:=c;
end;
procedure citire;
var i,x,y:longint;
begin
assign(input,'dfs.in'); reset(input);
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
adaug(x,y);
adaug(y,x);
end;
close(input);
end;
procedure df(i:longint);
var p:ref;
begin
sel[i]:=1;
p:=prim[i];
while p<>nil do
begin
if sel[p^.vf]=0 then df(p^.vf);
p:=p^.leg;
end;
end;
procedure rezolvare;
var i:longint;
begin
nr:=0;
for i:=1 to n do
if sel[i]=0 then
begin
df(i);
inc(nr);
end;
end;
begin
assign(output,'dfs.out'); rewrite(output);
citire;
rezolvare;
if nr=0 then writeln(1)
else writeln(nr);
close(output);
end.