Cod sursa(job #1438401)

Utilizator BLz0rDospra Cristian BLz0r Data 19 mai 2015 20:39:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;

#define Nmax 100002

FILE *f = fopen ( "ctc.in", "r" );
FILE *g = fopen ( "ctc.out", "w" );

vector < int > G[Nmax], CTC[Nmax];
bitset < Nmax > inStack;
stack < int > stiva;
int lowlink[Nmax], idx[Nmax], index = 1, ctc;

void Tarjan ( int nod ){

    if ( idx[nod] )
        return;

    vector < int > :: iterator it;

    idx[nod] = lowlink[nod] = index++;
    stiva.push ( nod );
    inStack[nod] = 1;

    for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
        if ( !idx[*it] ){
            Tarjan ( *it );
            lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
        }
        else{
            if ( inStack[*it] )
                lowlink[nod] = min ( lowlink[nod], idx[*it] );
        }
    }

    if ( lowlink[nod] == idx[nod] ){
        int k;
        ctc++;
        do{
            k = stiva.top();
            stiva.pop();
            inStack[k] = 0;
            CTC[ctc].push_back ( k );
        }while ( k != nod );
    }
}

int main(){

    int N, M, x, y;
    vector < int > :: iterator it;

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d", &x, &y );
        G[x].push_back ( y );
    }

    for ( int i = 1; i <= N; ++i )
        if ( !idx[i] )
            Tarjan ( i );

    fprintf ( g, "%d\n", ctc );

    for ( int i = 1; i <= ctc; ++i ){
        for ( it = CTC[i].begin(); it < CTC[i].end(); ++it )
            fprintf ( g, "%d ",*it );
        fprintf ( g, "\n" );
    }

    return 0;
}