Cod sursa(job #2255428)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 6 octombrie 2018 22:25:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define maxn 100000
#define maxm 200000

using namespace std;

vector <int> g[2][maxn+5];
int preord[maxn+5];
int ind_prd;
bool viz[2][maxn+5];
int n_ctc;
vector <int> rez[maxn+5];

void dfs ( int pin, int x )
{
  viz[pin][x] = 1;
  if ( pin == 1 )
    rez[n_ctc].push_back ( x + 1 );

  int sz = g[pin][x].size (), i, nod;
  for ( i = 0; i < sz; i++ )
  {
    nod = g[pin][x][i];
    if ( !viz[pin][nod] )
      dfs ( pin, nod );
  }
  if ( pin == 0 )
    preord[ind_prd++] = x;
}

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

  int n, m;

  fin >> n >> m;

  int i, x, y;

  for ( i = 0; i < m; i++ )
  {
    fin >> x >> y;
    g[0][x-1].push_back ( y - 1 );
  }
  /// dfs 1
  for ( i = 0; i < n; i++ )
    if ( !viz[0][i] )
      dfs ( 0, i );
  /// transp
  int j, sz;
  for ( i = 0; i < n; i++ )
  {
    sz = g[0][i].size ();
    for ( j = 0; j < sz; j++ )
      g[1][g[0][i][j]].push_back ( i );
  }

  /// dfs 2
  for ( i = n - 1; i >= 0; i-- )
  {
    j = preord[i];
    if ( !viz[1][j] )
    {
      dfs ( 1, j );
      n_ctc++;
    }
  }

  fout << n_ctc << '\n';
  for ( i = 0; i < n_ctc; i++ )
  {
    sz = rez[i].size ();
    for ( j = 0; j < sz; j++ )
      fout << rez[i][j] << ' ';
    fout.put ( '\n' );
  }

  fin.close ();
  fout.close ();

  return 0;
}