Cod sursa(job #2343541)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 14 februarie 2019 08:48:12
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#define NMAX 210
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int s[NMAX],vf=0,g[NMAX][NMAX],gt[NMAX][NMAX];
int n,m,i,nr,j;
int uz[NMAX];
int comp[NMAX][NMAX];
void citire();
void dfs(int k);void dfs1(int k);
int main()
{citire();
for(i=1;i<=n;i++)
    if(!uz[i])
        {
        dfs(i);
        }


   int x;
   for(i=1;i<NMAX;i++)
      uz[i]=0;
   ///reintializat
 while(vf)
        {
        x=s[vf--];
        if(!uz[x])
        {nr++;dfs1(x);}

        }

   fout<<nr<<'\n';
   for(i=1;i<=nr;i++)
    {for(j=1;j<=n;j++)
       if(uz[j]==i)
          {
          fout<<j<<" ";
          }
    fout<<'\n';
    }
    return 0;
}
void citire()
{int i,x,j,y;
   fin>>n>>m;
  for(i=1;i<=m;i++)
    {
    fin>>x>>y;
    g[x][++g[x][0]]=y;
    gt[y][++gt[y][0]]=x;
    }

}
void dfs(int k)
{int i;
 uz[k]=1;
    for(i=1;i<=g[k][0];i++)
        if(!uz[g[k][i]])
        {
         dfs(g[k][i]);
        }
     s[++vf]=k;
}
void dfs1(int k)
{int i;
 uz[k]=nr;comp[nr][++comp[nr][0]]=k;
    for(i=1;i<=gt[k][0];i++)
        if(!uz[gt[k][i]])
        {

         dfs1(gt[k][i]);
        }
}