Cod sursa(job #2680593)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 3 decembrie 2020 19:12:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb

#include <fstream>
#include <vector>
#include <stack>
#define f in
#define g out

using namespace std;
ifstream in ( "ctc.in" );
ofstream out( "ctc.out" );
int n, m, i, x, y, nivel, ctc;
int niv[100100], low[100100], fr[100100];
vector<int> L[100100], sol[100100];
stack<int> s;

void dfs( int nod ){

nivel++;
niv[nod] = nivel;
low[nod] = nivel;
s.push(nod);
fr[nod] = 1;

for ( auto vecin: L[nod] )
    if ( !niv[vecin] ){
        dfs(vecin);
        low[nod] = min ( low[nod], low[vecin] );
    } else if ( fr[vecin] )
        low[nod] = min ( low[nod], low[vecin] );

if ( niv[nod] == low[nod] ){
    ctc++;
    x = nod;
    do {
        x = s.top();
        sol[ctc].push_back(x);
        fr[x] = 0;
        s.pop();
    } while ( x != nod );
}

}

int main() {

f>>n>>m;
for ( i=1; i <= m; i++ ){
    f>>x>>y;
    L[x].push_back(y);
}

for ( i=1; i <= n; i++ )
    if ( !niv[i] )
        dfs(i);

g<<ctc<<"\n";
for ( i=1; i <= ctc; i++, g<<"\n" )
    for ( auto nod: sol[i] )
        g<<nod<<" ";
return 0;
}