Cod sursa(job #2884455)

Utilizator octavi26octavian octavi26 Data 3 aprilie 2022 17:38:01
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define N 100008

using namespace std;

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

int n, m;
vector<int> h[N], hinv[N];

void Citire()
{
    int i;
    int x, y;
    fin >> n >> m;
    for( i=1; i<=m; i++ )
    {
        fin >> x >> y;
        h[x].push_back(y);
        hinv[y].push_back(x);
    }
}

bool viz[N];
stack< int > st;

void dfs( int nod )
{
    viz[nod] = 1;
    for( auto fiu : h[nod] )
    {
        if( !viz[fiu] ) dfs(fiu);
    }
    st.push( nod );
}

int nrc;
vector<int> sol[N];

void dfs2( int nod )
{
    viz[nod] = 1;
    sol[nrc].push_back( nod );
    for( auto fiu : hinv[nod] )
    {
        if( !viz[fiu] ) dfs2(fiu);
    }
}

void Rezolvare()
{
    int i;
    for( i=1; i<=n; i++ )
    {
        if( !viz[i] ) dfs(i);
    }
    for( i=1; i<=n; i++ )
    {
        viz[i] = 0;
    }
    while( !st.empty() )
    {
        if( !viz[st.top()] ) nrc++, dfs2( st.top() );
        st.pop();
    }

    fout << nrc << "\n";
    for( i=1; i<=nrc; i++ )
    {
        for( auto fiu : sol[i] )
            fout << fiu << " ";
        fout << "\n";
    }
}

int main()
{
    Citire();
    Rezolvare();
    //cout << sizeof( Lee ) / 1024.0 / 1024.0;
    return 0;
}