Cod sursa(job #272306)

Utilizator FllorynMitu Florin Danut Flloryn Data 6 martie 2009 19:34:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.5 kb
type nod=^pnod;   
     pnod=record  
       inf:longint;   
       adr:nod;   
     end;   
  
var f,g:text;   
    a,ult:array[1..100000] of nod;   
    viz:array[1..100000] of boolean;   
    nou,nou2,p:nod;   
    n,m,i,nr:longint;   
  
procedure citire;   
  var x,y:longint;   
  begin  
    assign(f,'dfs.in');   
    reset(f);   
    readln(f,n,m);   
    for i:=1 to m do begin  
      readln(f,x,y);   
      new(nou);   
      nou^.inf:=y;   
      new(nou2);   
      nou2^.inf:=x;   
      if a[y]=nil then begin  
        a[y]:=nou2;   
        ult[y]:=a[y];   
      end else begin  
        ult[y]^.adr:=nou2;   
        ult[y]:=nou2;   
      end;   
      if a[x]=nil then begin  
        a[x]:=nou;   
        ult[x]:=a[x];   
      end else begin  
        ult[x]^.adr:=nou;   
        ult[x]:=nou;   
      end;   
    end;   
  end;   
  
procedure dfs(i:longint);   
  var p:nod;   
  begin  
    viz[i]:=true;   
    if a[i]<>nil then begin  
      p:=a[i];   
      while p<>nil do begin  
        if viz[p^.inf]=false then dfs(p^.inf);   
        p:=p^.adr;   
      end;   
    end;   
  end;   
  
procedure conexe;   
  begin  
    for i:=1 to n do  
      if not viz[i] then begin  
        nr:=nr+1;   
        dfs(i);   
      end;   
  end;   
  
procedure afisare;   
  begin  
    assign(g,'dfs.out');   
    rewrite(g);   
    write(g,nr);   
    close(g);   
  end;   
  
begin  
  citire;   
  conexe;   
  afisare;   
end.