Cod sursa(job #176251)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 10 aprilie 2008 21:43:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.01 kb
type lista=^element;
     element=record
                i:longint;
                a:lista;
              end;
var l:array[1..100001] of lista;
    x,y,n,m,i:longint;
    p:lista;
    viz:array[1..100001] of longint;
procedure dfs(i:longint);
     var q:lista;
     begin
       inc(y);
       q:=l[i];
       while q<>nil do
         begin
         if viz[q^.i]=0 then
         begin
           viz[q^.i]:=x;
           dfs(q^.i);
         end;
           q:=q^.a;
         end;
     end;

begin
assign(input,'dfs.in'); reset(input);
assign(output,'dfs.out'); rewrite(output);
readln(n,m);
for i:=1 to m do
   begin
     read(x,y);
     new(p);
     p^.i:=y;
     p^.a:=l[x];
     l[x]:=p;
     new(p);
     p^.i:=x;
     p^.a:=l[y];
     l[y]:=p;
   end;
for i:=1 to n do viz[i]:=0;
i:=1;
x:=1;
y:=0;
while i<=n do
    begin
      if (viz[i]=0)and(l[i]<>nil) then begin viz[i]:=x;dfs(i);inc(x); end;
      inc(i);
    end;
writeln(x-1+n-y);
close(input);
close(output);
end.