Cod sursa(job #1251029)

Utilizator serban.cobzacCobzac Serban serban.cobzac Data 28 octombrie 2014 21:08:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <vector>
#define DMAX 100005
using namespace std;
FILE*fin=fopen("ctc.in","r");
FILE*fout=fopen("ctc.out","w");

vector <int> G[DMAX];
vector <int> T[DMAX];
vector <int> sol[DMAX];
int n, m, nrctc, pozpo;
int uz[DMAX];
int postord[DMAX];

void citire();
void rezolvare();
void DFSG(int vf);
void DFST(int vf);
void afisare();

int main(){
    citire();
    rezolvare();
    afisare();
    return 0;
}

void citire(){
    int x, y;
    fscanf(fin, "%d%d", &n, &m);
    for(int i=1; i<=m; ++i){
        fscanf(fin, "%d%d", &x, &y);
        G[x].push_back(y);
        T[y].push_back(x);
    }
}

void rezolvare(){
    int i;
    for(i=1; i<=n; i++)
        if(!uz[i])
            DFSG(i);
    for(i=1; i<=n; ++i) uz[i]=0;
    for(i=n; i>0; --i)
        if(!uz[postord[i]]){
            nrctc++;
            DFST(postord[i]);
        }
}

void DFSG(int vf){
    uz[vf]=1;
    for(int i=0; i<G[vf].size(); ++i)
        if(!uz[G[vf][i]])
            DFSG(G[vf][i]);
    postord[++pozpo]=vf;
}

void DFST(int vf){
    sol[nrctc].push_back(vf);
    uz[vf]=1;
    for(int i=0; i<T[vf].size(); ++i)
        if(!uz[T[vf][i]])
            DFST(T[vf][i]);
}

void afisare(){
    int i, j;
    fprintf(fout, "%d\n", nrctc);
    for(i=1; i<=nrctc; ++i){
        for(j=0; j<sol[i].size(); ++j)
        fprintf(fout, "%d ", sol[i][j]);
        fprintf(fout, "\n");
    }
    fclose(fout);
}