Cod sursa(job #1607498)

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

using namespace std;

vector <int> vec [MAXN];
vector <int> vecT[MAXN];
vector <int> c[MAXN];

int N, M, v[MAXN], nr, R;
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);
        vec [x].push_back(y);
        vecT[y].push_back(x);

    }

}

void dfs( int k ){
int i;

    viz[k] = 1;
    for(i=0;i<vec[k].size();i++)
        if( viz[ vec[k][i] ] == 0 )
            dfs( vec[k][i] );
    v[++nr] = k;
}

void dfsT( int k ){
int i;

    c[R].push_back(k);

    viz[k] = 1;
    for(i=0;i<vecT[k].size();i++)
        if( viz[ vecT[k][i] ] == 0 )
            dfsT( vecT[k][i] );
}

void Rezolvare(){
int i, j;

    nr = 0;
    for(i=1;i<=N;i++)
        if( viz[i] == 0 )
            dfs(i);

    memset(viz,0,sizeof(viz));

    R = 0;
    for(i=N;i>=1;i--)
        if( viz[v[i]] == 0 ){
            R++;
            dfsT( v[i] );
        }

    fprintf(g,"%d\n",R);
    for(i=1;i<=R;i++){

        for(j=0;j<c[i].size();j++)
            fprintf(g,"%d ",c[i][j]);
        fprintf(g,"\n");

    }
}

int main(){

    Citire();

    Rezolvare();

return 0;
}