Cod sursa(job #2928591)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 23 octombrie 2022 14:08:53
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
#include <vector>
#define N 100000

std::vector <std::vector<int>> g, revg, ans;

bool parc[N], vizitat[N];
char marked[N];
int n;

void init() {
    for ( int i = 0; i < n; i ++ )
        parc[i] = false;
}

void dfs( std::vector <std::vector<int>> g, int node ) {
    parc[node] = true;
    marked[node] ++;
    for ( int i = 0; i < g[node].size(); i ++ )
        if ( !parc[g[node][i]] )
            dfs( g, g[node][i] );
}

void conex( int node ) {
    init();
    dfs( g, node );

    init();
    dfs( revg, node );

    std::vector <int> aux;
    for ( int i = 0; i < n; i ++ ) {
        if ( marked[i] == 2 ) {
            vizitat[i] = true;
            aux.push_back( i );
        }
        marked[i] = 0;
    }
    ans.push_back( aux );
}

int main() {
    FILE *fin, *fout;
    int m, x, y;

    fin = fopen( "ctc.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    g.resize( n );
    revg.resize( n );
    for ( int i = 0; i < m; i ++ ) {
        fscanf( fin, "%d%d", &x, &y );
        x --;
        y --;
        g[x].push_back( y );
        revg[y].push_back( x );
    }
    fclose( fin );

    for ( int i = 0; i < n; i ++ )
        if ( !vizitat[i] )
            conex( i );

    fout = fopen( "ctc.out", "w" );
    fprintf( fout, "%d\n", ans.size() );
    for ( int i = 0; i < ans.size(); i ++ ) {
        for ( int j = 0; j < ans[i].size(); j ++ )
            fprintf( fout, "%d ", ans[i][j] + 1 );
        fprintf( fout, "\n" );
    }
    fclose( fout );
    return 0;
}