Cod sursa(job #1249769)

Utilizator Lucian_BosinceanuLucian-Andrei Bosinceanu Lucian_Bosinceanu Data 27 octombrie 2014 13:46:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#define DMAX 5000

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

void citire();
void rezolvare();
//void DFS(int vf,int uz[],int matr[][DMAX]);
void DFSA(int vf);
void DFST(int vf);
void get_ctc();
void clear();
void afisare();

int A[DMAX][DMAX];
int T[DMAX][DMAX];
int sol[DMAX][DMAX];
int uz1[DMAX], uz2[DMAX], uzt[DMAX];
int n,m,nrctc;

int main()
{
citire();
rezolvare();
afisare();
    return 0;
}

void citire()
{
int i,x,y;
fin>>n>>m;
for (i=1;i<=m;i++)
     {
      fin>>x>>y;
      A[x][0]++;
      A[x][ A[x][0] ]=y;
      T[y][0]++;
      T[y][ T[y][0] ]=x;
     }
}

void rezolvare()
{
int i;
for (i=1;i<=n;i++)
     if (uzt[i]==0)
     {
      //DFS(i,uz1,A);
      //DFS(i,uz2,T);
      DFSA(i);
      DFST(i);
      get_ctc();
      clear();
     }
}

void get_ctc()
{
int i,j;
for (i=1;i<=n;i++)
     if (uz1[i]==(uz2[i]==1))
         {
          nrctc++;
          //fout<<"Componenta tare conexa numarul "<<nrctc<<": ";
          for (j=i;j<=n;j++)
               if (uz1[j]==(uz2[j]==1))
                   {
                    uzt[j]=1;
                    sol[nrctc][ ++sol[nrctc][0] ]=j;
            //        fout<<j<<' ';
                   }
          //fout<<'\n';
          return;
         }
}

void clear()
{
int i;
for (i=1;i<=n;i++) uz1[i]=uz2[i]=0;
}

void DFSA(int vf)
{
int i;
uz1[vf]=1;
for (i=1;i<=A[vf][0];i++)
     if ( uz1[ A[vf][i] ]==0 ) DFSA(A[vf][i]);
}

void DFST(int vf)
{
int i;
uz2[vf]=1;
for (i=1;i<=T[vf][0];i++)
     if ( uz2[ T[vf][i] ]==0 ) DFST(T[vf][i]);
}

void afisare()
{
int i,j;
fout<<nrctc<<'\n';
for (i=1;i<=nrctc;i++)
     {for (j=1;j<=sol[i][0];j++)
          fout<<sol[i][j]<<' ';
     fout<<'\n';
     }
}