Cod sursa(job #2502849)

Utilizator robx12lnLinca Robert robx12ln Data 1 decembrie 2019 18:01:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int DIM = 1e5 + 5;

int K, N, M, low[DIM], niv[DIM], f[DIM], cod;
vector<int> edge[DIM];
vector<int> ctc[DIM];
stack<int> st;

void dfs( int nod ){
    niv[nod] = low[nod] = ++cod;
    f[nod] = 1;
    st.push( nod );
    for( int i = 0; i < edge[nod].size(); i++ ){
        int vec = edge[nod][i];
        if( niv[vec] == 0 ){
            dfs( vec );
            low[nod] = min( low[nod], low[vec] );
        }else{
            if( f[vec] == 1 )
                low[nod] = min( low[nod], low[vec] );
        }
    }
    if( low[nod] == niv[nod] ){
        K++;
        while( st.top() != nod ){
            ctc[K].push_back( st.top() );
            f[ st.top() ] = 0;
            st.pop();
        }
        st.pop();
        f[nod] = 0;
        ctc[K].push_back( nod );
    }
    return;
}

int main(){

    fin >> N >> M;
    for( int i = 1; i <= M; i++ ){
        int x, y; fin >> x >> y;
        edge[x].push_back( y );
    }

    cod = 0;
    for( int i = 1; i <= N; i++ ){
        if( niv[i] == 0 )
            dfs( i );
    }

    fout << K << "\n";
    for( int i = 1; i <= K; i++, fout << "\n" )
        for( int j = 0; j < ctc[i].size(); j++, fout << " " )
            fout << ctc[i][j];
    return 0;
}