Cod sursa(job #2314333)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 8 ianuarie 2019 12:47:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

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

const int NMAX = 100005;

int N, M;

vector <int> Ad[NMAX];
vector <int> Ad_rev[NMAX];

vector <int> T;

bool vis[NMAX];

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 Topo( int nod )
{
  vis[nod] = true;

  int w;

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

    if( !vis[w] ) Topo( w );
  }

  T.push_back( nod );
}

void DFS( int nod, bool printt )
{
  vis[nod] = true;

  if( printt ) fout << nod << ' ';

  int w;

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

    if( !vis[w] ) DFS( w, printt );
  }
}

void Do()
{
  for( int i = 1; i <= N; ++i )
   if( !vis[i] )
     Topo( i );

  int w;

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

      Ad_rev[w].push_back(i);
    }
  }

  int nr_comp = 0;

  for( int i = 0; i <= N; ++i )
    vis[i] = 0;

  for( int i = T.size() - 1; i >= 0; --i )
   if( vis[T[i]] == false )
    {
      ++nr_comp;
      DFS( T[i], false );
    }

  fout << nr_comp << '\n';

  for( int i = 0; i <= N; ++i )
    vis[i] = 0;

  for( int i = T.size() - 1; i >= 0; --i )
   if( vis[T[i]] == false )
    {
      ++nr_comp;
      DFS( T[i], true );

      fout << '\n';
    }

  fout.close();
}

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

    return 0;
}