Cod sursa(job #1923364)

Utilizator DysKodeTurturica Razvan DysKode Data 10 martie 2017 23:03:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

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

/*
stack< pair<int,int> > st;
vector< int > G[ 100010 ] , sol[100010];*/
int idx[100010],mini[100010],ans,a,b,x,y,n,m,i,instack[100010];
stack< int > st;
vector< int > G[ 100010 ],CTC[100010];

void DF( int nod )
{
    mini[ nod ] = idx[ nod ] = ++idx[ 0 ];
    instack[ nod ] = 1;
    st.push( nod );
    for( auto it : G[ nod ] )
    {
        if( !idx[ it ] )
            DF( it );
        if( instack[ it ] )
            mini[ nod ] = min( mini[ nod ] , mini[ it ] );
    }

    if( mini[ nod ] == idx[ nod ] )
    {
        ++ans;
        while( st.top() != nod )
        {
            CTC[ ans ].push_back( st.top() );
            instack[ st.top() ] = 0;
            st.pop();
        }
        CTC[ ans ].push_back( st.top() );
        instack[ nod ] = 0;
        st.pop();
    }
}

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        G[ x ].push_back( y );
    }

    for( i = 1 ; i <= n ; i++ )
    {
        if( !idx[ i ] )
        {
            DF( i );
        }
    }
    fout<<ans<<'\n';
    for( i = 1 ; i <= ans ; i++ )
    {
        for( auto it : CTC[ i ] )
            fout<<it<<' ';
        fout<<'\n';
    }

return 0;
}