Pagini recente » Cod sursa (job #1683797) | Istoria paginii runda/test_pozitiv | Cod sursa (job #1934444) | Cod sursa (job #217626) | Cod sursa (job #210831)
Cod sursa(job #210831)
{
Determinarea componentelor
conexe prin parcurgerea in
latime a grafului
}
type adr=^noduri;
noduri=record val:longint; urm:adr; end;
var L:array[1..100000] of adr;
E:array[1..100000] of boolean;
C:array[1..100000] of longint;
n,m,i,j,k,p,u,kont:longint;
q:adr;
f:text;
procedure bf(nod:longint);
begin
p:=1; u:=1; C[1]:=nod;
E[nod]:=true;
while p<=u do
begin
q:=L[C[p]];
while q<>nil do
begin
if not E[q^.val] then
begin
inc(u);
C[u]:=q^.val;
E[q^.val]:=true;
end;
q:=q^.urm;
L[C[p]]:=L[C[p]]^.urm;
end;
inc(p);
end;
end;
begin
assign(f,'dfs.in');
reset(f);
readln(f,n,m);
for k:=1 to m do
begin
readln(f,i,j);
new(q);
q^.val:=j; q^.urm:=L[i];
L[i]:=q;
new(q);
q^.val:=i; q^.urm:=L[j];
L[j]:=q;
end;
close(f);
kont:=0;
for i:=1 to n do
if not E[i] then begin inc(kont); bf(i); end;
assign(f,'dfs.out');
rewrite(f);
write(f,kont);
close(f);
end.