Cod sursa(job #3252945)

Utilizator Ana_22Ana Petcu Ana_22 Data 31 octombrie 2024 16:08:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100001
using namespace std;

int viz[NMAX];

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

void dfs( int node, vector<int> edges[NMAX], vector<int>& add_to ) {
    viz[node] = 1;
    for( unsigned int i = 0; i < edges[node].size(); i++ ) {
        int newnode = edges[node][i];
        if( !viz[newnode] )
            dfs( newnode, edges, add_to );
    }
    add_to.push_back( node );
}

int main() {
    vector <int> edg[NMAX];
    vector <int> gt[NMAX];
    vector <int> st;
    vector <int> ctc[NMAX];
    int n, m, x, y;
    fin >> n >> m;
    for( int i = 0; i < m; i++ ) {
        fin >> x >> y;
        edg[x].push_back( y );
        gt[y].push_back( x );
    }
    for( int node = 1; node <= n; node++ ) {
        if( !viz[node] )
            dfs( node, edg, st );
    }
    for( int node = 1; node <= n; node++ ) viz[node] = 0;
    
    int cnt = 1;
    for( int i = (int)st.size() - 1; i >= 0; i-- ) {
        if( !viz[st[i]] )
            dfs( st[i], gt, ctc[cnt++] );
    }
    cnt--;
    
    fout << cnt << '\n';
    for( int i = 1; i <= cnt; i++ ) {
        for( unsigned int j = 0; j < ctc[i].size(); j++ )
            fout << ctc[i][j] << ' ';
        fout << '\n';
    }
    return 0;
}