Cod sursa(job #2098347)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 2 ianuarie 2018 18:02:45
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#define nmax 10000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,succ[nmax],pred[nmax],a[nmax][nmax],x,y;
void df_s(int x, int mark)
{
    succ[x]=mark;
    for(int i = 1; i <= n ; i++)
        if(a[x][i]&& !succ[i])
          df_s(i,mark);
}
void df_p(int x, int mark)
{
    pred[x]=mark;
    for(int i =1; i<= n ; i++)
         if(a[i][x] && !pred[i])
          df_p(i,mark);
}
int main()
{
      fin>>n>>m;
      for(int i =1; i <= m ; i++)
      {
          fin>>x>>y;
          a[x][y]=1;
      }
       int ctc=0;
       for(int i =1; i <= n ; i++)
        if(!succ[i])
       {
           ctc++;
           df_s(i,ctc);
           df_p(i,ctc);
           for(int j =1 ; j <= n ; j ++)
              if(succ[j]!= pred[j])
                succ[j]=pred[j]=0;

       }
       fout<<ctc<<" "<<'\n';
       for(int i =1 ; i <= ctc; i++)
           {
               for(int j =1; j <= n ; j ++)
               {
                    if(succ[j]==i) fout<<j<<" ";
               }
                fout<<'\n';
           }






    return 0;
}