Cod sursa(job #1987842)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 1 iunie 2017 11:41:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

#define ll long long
#define pb push_back

using namespace std;

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

const int NLIM = 1e5 + 10;

int N, M;
vector< int > graph[NLIM];
vector< int > rgraph[NLIM];

int strong[NLIM];
vector< int > res[NLIM];
int resnr = 0;

int dfs[NLIM];
vector< int > top;

void f( int nod )
{
   // cout << nod << "\n";
    dfs[nod] = 1;
    for( int j = 0; j < graph[nod].size(); ++j )
    {
        int nnod = graph[nod][j];
        if( !dfs[nnod] )
            f( nnod );
    }
    top.pb( nod );
}

void s( int nod )
{
    strong[nod] = 1;
    res[resnr].pb( nod );
    for( int j = 0; j < rgraph[nod].size(); ++j )
    {
        int nnod = rgraph[nod][j];
        if( !strong[nnod] )
            s( nnod );
    }
}




int main()
{
    fin >> N >> M;
    for( int i = 0; i < M; ++i )
    {
        int x, y;
        fin >> x >> y;
        graph[x].pb( y );
        rgraph[y].pb( x );
    }

    for( int i = 1; i <= N; ++i )
        if( !dfs[i] )
        {
            f( i );
            top.pb( i );
        }


    for( int i = top.size() - 1; i >= 0; --i )
        if( !strong[top[i]] )
        {
            s( top[i] );
            ++resnr;
        }

    fout << resnr << "\n";
    for( int i = 0; i < resnr; ++i )
    {
        for( int j = 0; j < res[i].size(); ++j )
        {
            fout << res[i][j] << " ";
        }
        fout << "\n";
    }

    return 0;
}