Cod sursa(job #2105806)

Utilizator IustinSSurubaru Iustin IustinS Data 14 ianuarie 2018 12:35:59
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#define nmax 1001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int lista[nmax][nmax];
int listaT[nmax][nmax];
int n,m,k,nr;
int postord[nmax];
bool ver[nmax];
int ctc[nmax];

void citire();
void DFS(int vf);
void DFST(int vf);
void afisare();

int main()
{int i;
    citire();
    for (i=1; i<=n; i++)
      if (!ver[i])
         DFS(i);
    for (i=n; i>=1; i--)
      {
         if (ver[postord[i]])
            {k++;
             DFST(postord[i]);
            }
      }
    afisare();
    return 0;
}
void citire()
{
   int i,j,x,y;
   fin>>n>>m;
   for (i=1; i<=m; i++)
      {
         fin>>x>>y;
         lista[x][0]++;
         listaT[y][0]++;
         lista[x][lista[x][0]]=y;
         listaT[y][listaT[y][0]]=x;
      }
}
void DFS(int vf)
{int i;

   ver[vf]=1;
   for (i=1; i<=lista[vf][0]; i++)
      {
         if (!ver[lista[vf][i]])
            DFS(lista[vf][i]);
      }
   postord[++nr]=vf;
}
void DFST(int vf)
{
   int i;
   ver[vf]=0;
   ctc[vf]=k;
   for (i=1; i<=listaT[vf][0]; i++)
      {
            if (ver[listaT[vf][i]])
               DFST(listaT[vf][i]);
      }
}
void afisare()
{int i,j;
   fout<<k<<'\n';
   for (i=1; i<=k; i++)
      {for (j=1; j<=n; j++)
         if (ctc[j]==i)
            fout<<j<<' ';
      fout<<'\n';
      }

}