Cod sursa(job #2175709)

Utilizator Victor24Vasiesiu Victor Victor24 Data 16 martie 2018 18:36:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

int n, a, b, m, ctc;

ifstream f ("ctc.in");
ofstream g ("ctc.out");

vector < int > G[100005], GT[100005], rsp[100005];

bitset <100005> fv;

stack < int > st;

void dfs_1( int nod )
{
    fv[nod] = true;

    for ( auto i : G[nod] )
    {
        if ( fv[i] == false )
        {
            dfs_1( i );
        }
    }

    st.push(nod);

}

void dfs_2( int nod )
{
    fv[nod] = true;

    for ( auto i : GT[nod] )
    {
        if ( fv[i] == false )
        {
            dfs_2( i );
        }
    }

    rsp[ctc].push_back( nod );

}

int main ()
{
    f>>n>>m;

    for ( int i = 1; i <= m ; i++ )
    {
        f>>a>>b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }

    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( fv[i] == false )
        {
            dfs_1( i );
        }
    }

    fv.reset();

    while ( !st.empty() )
    {
        if ( fv[st.top()] == false )
        {
            ctc++;
            dfs_2( st.top() );
        }
        st.pop();
    }

    g<<ctc<<'\n';

    for ( int i = 1; i <= ctc ; i++ )
    {
        for ( auto it : rsp[i] )
        {
            g<<it<<" ";
        }
        g<<'\n';
    }

}