Cod sursa(job #2217737)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 1 iulie 2018 20:24:18
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

int N;
int M;
int nr_noduri;

vector <vector <int> > Ad(100002);

int disc[100002];
int low[100002];

deque <int> Stack;
bool in_stack[100002];

vector <vector <int> > SCC(100002);
int nr_scc;

void Read()
{
  fin >> N >> M;

  int x,y;

  for( int i = 1; i <= M; ++i )
  {
    fin >> x >> y;

    Ad[x].push_back(y);
  }

  fin.close();
}

void Discover( int nod, int parent )
{
   disc[nod] = low[nod] = ++nr_noduri;

   Stack.push_back( nod );
   in_stack[nod] = 1;

   int w;

   for( int i = 0; i < Ad[nod].size(); ++i )
   {
     w = Ad[nod][i];

     //if( w == parent ) continue;

     if( disc[w] == 0 )
     {
       Discover( w, nod );
       low[nod] = min( low[nod], low[w] );
     }
     else
       if( in_stack[w] )
         low[nod] = min( low[nod], disc[w] );
   }

   if( disc[nod] == low[nod] )
   {
     ++nr_scc;

     while( Stack.back() != nod )
     {
       SCC[nr_scc - 1].push_back( Stack.back() );

       in_stack[Stack.back()] = 0;

       Stack.pop_back();
     }

     SCC[nr_scc - 1].push_back( Stack.back() );
     Stack.pop_back();
   }
}

void Test()
{
  for( int i = 1; i <= N; ++i )
    fout << "NODUL : " << i << ' ' << disc[i] << ' ' << low[i] << '\n';


}

void Do()
{
   for( int i = 1; i <= N; ++i )
     if( disc[i] == 0 )
      Discover( i , i );
}

void Print()
{
  fout << nr_scc << '\n';

  for( int i = 0; i < nr_scc; ++i )
  {
    for( int j = 0; j < SCC[i].size(); ++j )
      fout << SCC[i][j] << ' ';

    fout << '\n';
  }

  fout.close();
}

int main()
{
    Read();
    Do();
    Print();

    return 0;
}