Cod sursa(job #1607553)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 21 februarie 2016 13:00:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
#define MAXN 100005
FILE *f=fopen("ctc.in","r"), *g=fopen("ctc.out","w");

using namespace std;

vector <int> v[MAXN], c[MAXN];

stack <int> ST;

int N, M, R=0, t=0, low[MAXN], niv[MAXN];
bool viz[MAXN];

void Citire(){
int i, x, y;

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

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

}

void dfs( int k ){
int i, NEWk, x;

    t++;
    viz[k] = 1;
    low[k] = niv[k] = t;

    ST.push(k);

    for(i=0;i<v[k].size();i++){

        NEWk = v[k][i];

        if( viz[ NEWk ] == 0 ){
            dfs(NEWk);
            low[k] = min( low[k], low[NEWk] );
        }
        else{
            low[k] = min( low[k], niv[NEWk] );
        }

    }

    if( niv[k] == low[k]){

        R++;
        do{
            x =ST.top();
            c[R].push_back(x);
            niv[k] = 1<<30;
            ST.pop();
        } while( k != x );

    }

}

int main(){

    Citire();

    for(int i=1;i<=N;i++)
        if( niv[i] == 0 )
        {
            t=0;
            dfs(i);
        }
    fprintf(g,"%d\n",R);
    for(int i=1;i<=R;i++){
        for(int j=0;j<c[i].size();j++)
            fprintf(g,"%d ",c[i][j]);
        fprintf(g,"\n");
    }

return 0;
}