Cod sursa(job #535689)

Utilizator david_raucaRauca Ioan David david_rauca Data 17 februarie 2011 17:08:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include<fstream>
#include<vector>
using namespace std;

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

int n, m, nrc, c;                   // nrc = nr de componente conexe,    c = contor in stiva

vector<vector<int> > G;
vector<vector<int> > T;
vector<vector<int> > sol;

int a[100001];                         //stiva
bool s[100001];                        // sirul de selectati in graful normal;
bool s1[100001];                       //sirul de selectati in graful transpus;

void Read();
void Solve();
void DF(int x);
void DFT(int x);

int main()
{
    Read();
    Solve();
    
    fin.close();
    fout.close();
    
    return 0;
}

void Read()
{
     fin >> n >> m;
     G.resize(n+1);
     T.resize(n+1);
     sol.resize(n+1);
     int x, y;
     while( fin >> x >> y )
     {
            G[x].push_back(y);
            T[y].push_back(x);
     }
}

void Solve()
{
     c = 0;
     for( int i = 1; i <= n; ++i )
     if( !s[i] )
     {
          DF(i);
          c++;
          a[c] = i;
     }
     /*
     for( int i = 1; i <= n; ++i )
          fout << a[i] << ' ';
     fout << '\n';
     */
     for( int i = n; i >= 1; --i )
          if( !s1[ a[i] ] )
          {
              nrc++;
              DFT( a[i] );
          }
     
     fout << nrc << '\n';
     
     for( int i = 1; i <= nrc; ++i )
     {
          for( int j = 0; j < sol[i].size(); ++j )
               fout << sol[i][j] << ' ';
          fout << '\n';
     }
}

void DF( int x )
{
     s[x] = true;
     for( int i = 0; i < G[x].size(); ++i )
          if( !s[ G[x][i] ] )
          {
              DF( G[x][i] );
              c++;
              a[c] = G[x][i];
          }
}

void DFT( int x )
{
     s1[x] = true;
     sol[nrc].push_back( x );
     
     for( int i = 0; i < T[x].size(); ++i )
          if( !s1[ T[x][i] ] )
              DFT( T[x][i] );
}