Cod sursa(job #699679)

Utilizator amaliutzzaGoia Amalia amaliutzza Data 29 februarie 2012 20:47:03
Problema Componente tare conexe Scor 30
Compilator fpc Status done
Runda Arhiva educationala Marime 1.92 kb
program comptareconexe; //cu matr de adiacenta

var fi,fo:text;
    n,m,i,dimst,nrel,j,nrcomp:integer;
    a,t:array of array of integer;
    matcomp:array[0..1000,0..1000]of integer;
    st,viz,viz2:array[0..100000]of integer;

  procedure citire;
  var i,x,y:integer;
  begin
      readln(fi,n,m);
      setlength(a,n+1,1);
      setlength(t,n+1,1);
      for i:=1 to m do
        begin
            readln(fi,x,y);
            setlength(a[x], length(a[x])+1);
            setlength(t[y], length(t[y])+1);
            inc(a[x,0]);
            a[x,a[x,0]]:=y;
            inc(t[y,0]);
            t[y,t[y,0]]:=x;
        end;
  end;

  procedure df(nod:integer);
  var i:integer;
  begin
      viz[nod]:=1;
      for i:=1 to a[nod,0] do
        begin
            if viz[a[nod,i]]=0 then
              df(a[nod,i]);
        end;
      inc(dimst);
      st[dimst]:=nod;
  end;

  procedure dfst(nod:integer);
  var i:longint;
  begin
      viz2[nod]:=1;
      inc(nrel);
      matcomp[nrcomp,nrel]:=nod;
      for i:=1 to t[nod,0] do
        if viz2[t[nod,i]]=0 then
          dfst(t[nod,i]);
  end;

begin
    assign(fi,'ctc.in'); reset(fi);
    assign(fo,'ctc.out'); rewrite(fo);

      citire;

      //prima parcurgere
      for i:=1 to n do
        if viz[i]=0 then
          df(i);

      //parcurgerea pe graf transpus
      // se memoreaza comp conexe in matricea matcomp

      for i:=dimst downto 1 do
        begin
            if viz2[st[i]]=0 then
              begin
                  inc(nrcomp);
                  nrel:=0; //din comp conexa curenta
                  dfst(st[i]);
                  matcomp[nrcomp,0]:=nrel;
              end;
        end;

     writeln(fo,nrcomp);
     for i:=1 to nrcomp do
       begin
           for j:=1 to matcomp[i,0] do
             write(fo, matcomp[i,j],' ');
           writeln(fo);
       end;

    close(fi); close(Fo);
end.