Cod sursa(job #2509828)

Utilizator XsoundCristian-Ioan Roman Xsound Data 14 decembrie 2019 22:44:52
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;

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

vector < int > g[Nmax], gt[Nmax], rev, cicle[Nmax/3];

bitset < Nmax > b;

int n, m, contor;

void read ( );

void DFS ( int x );
void DFS2 ( int x );

int main ( )
{
    read ( );

    for ( int i = 1;  i <= n; i++ )
        if ( b[i] == 0 )
            DFS ( i );

    int lng = rev.size();

    b.reset();

    for ( int i = lng - 1; i >=0 ; i-- )
    {
        if ( b[rev[i]] == 0 )
        contor++,DFS2 ( rev[i] );
    }

    for ( int i = 1; i <= contor; i++ )
    {
        lng = cicle[i].size();

        for ( int j = 0; j < lng ; j++ )
            fout << cicle[i][j] << ' ';

        fout << '\n';
    }
}

void DFS2 ( int x )
{
    b[x] = 1;

    int lng = gt[x].size(), node;

    for ( int i = 0; i < lng ; i++ )
    {
        node = gt[x][i];

        if ( b[node] == 0 )
            DFS2 ( node );
    }

    cicle[contor].push_back(x);
}

void DFS ( int x )
{
    b[x] = 1;
    int lng = g[x].size(), node;
    for ( int i = 0; i < lng ; i++ )
    {
        node = g[x][i];

        if ( b[node] == 0 )
            DFS ( node );
    }

    rev.push_back(x);
}

void read ( )
{
    int x, y;

    fin >> n >> m;

    for ( int i = 1; i <= m; i++ )
    {
        fin >> x >> y;

        g[x].push_back(y);
        gt[y].push_back(x);
    }
}