Cod sursa(job #3280660)

Utilizator pacelaaaCiurea Pavel pacelaaa Data 27 februarie 2025 00:11:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

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

#define cin fin
#define cout fout
#define PB push_back

const int Nmax = 1e5;

vector<int> out[Nmax + 1], in[Nmax + 1];
vector< vector<int> > comp;
bool processed[Nmax+1];
vector<int> l;

inline void dfs ( int nod ) {
  int i, nod2;

  if ( !processed[nod] ) {
    processed[nod] = true;
    for ( i = 0; i < out[nod].size(); i ++ ) {
      nod2 = out[nod][i];
      if ( !processed[nod2] )
        dfs( nod2 );
    }
    l.PB( nod );
  }
}

inline void dfs2 ( int nod ) {
  int i, nod2;
  if ( !processed[nod] )
    comp.PB( {nod} );
  processed[nod] = true;

  for ( i = 0; i < in[nod].size(); i ++ ) {
    nod2 = in[nod][i];
    if ( !processed[nod2] ) {
      processed[nod2] = true;
      comp[comp.size()-1].PB( nod2 );
      dfs2( nod2 );
    }
  }
}

int main()
{
    int n, m, nod1, nod2, i, j;

    cin >> n >> m;
    for ( i = 0; i < m; i ++ ) {
      cin >> nod1 >> nod2;
      out[nod1].PB( nod2 );
      in[nod2].PB( nod1 );
    }

    for ( i = 1; i<=n; i ++ )
      dfs( i );
    for ( i = 1; i <=n; i ++ )
      processed[i] = false;


    for ( i =  n - 1; i >= 0; i -- ) {
      dfs2( l[i] );
    }


    cout << comp.size() << "\n";
    for ( i = 0; i < comp.size(); i ++ ) {
      for ( j = 0; j < comp[i].size(); j ++ )
        cout << comp[i][j] << " ";
      cout << "\n";
    }

    return 0;
}