Cod sursa(job #151067)

Utilizator petrePajarcu Alexandru-Petrisor petre Data 7 martie 2008 19:41:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.95 kb
var x:array[1..400001] of longint;
    y,z:array[1..100002] of longint;

n,m,i,j,k,p:longint;

procedure citire;
var a,b:array[1..200001] of longint;
begin
for i:=1 to m do
    begin
    readln(a[i],b[i]);
    inc(y[a[i]]);
    inc(y[b[i]]);
    end;
for i:=2 to n do
    y[i]:=y[i-1]+y[i];
for i:=1 to m do
    begin
    x[y[a[i]]]:=b[i];
    dec(y[a[i]]);
    x[y[b[i]]]:=a[i];
    dec(y[b[i]]);
    end;
y[n+1]:=2*m;
end;

procedure det(p,k:longint);
var j:longint;
begin
z[p]:=k;
for j:=y[p]+1 to y[p+1] do
              if z[x[j]]=0 then
                        det(x[j],k);
end;
procedure dfs;
begin
k:=0;
for i:=1 to n do
       if z[i]=0 then
                 begin
                 inc(K);
                 det(i,k);
                 end;
end;

begin
assign(input,'dfs.in');
assign(output,'dfs.out');
reset(input);
rewrite(output);
readln(n,m);
citire;
dfs;
writeln(K);
close(input);
close(output);
end.