Cod sursa(job #1250755)

Utilizator Andrei_TirpescuAndrei Tirpescu Andrei_Tirpescu Data 28 octombrie 2014 15:44:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#define NMAX 100001

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, vfi;
vector<int> A[NMAX], At[NMAX], Rez[NMAX];
bool uz[NMAX], uz2[NMAX];
int postordine[NMAX], nr, lgrez = 1, lg2;

void init();
void DFS1(int);
void DFST(int);

int main(){
    init();
    int i;
    for(i = 1; i<=n; ++i){
        if(!uz[i]) DFS1(i);
    }



    for(i = nr; i>=1; --i){
        if(!uz2[postordine[i]]){
            lg2= 0;
            DFST(postordine[i]);
            lgrez++;
        }
    }
    lgrez--; int j;
    fout<<lgrez<<'\n';
    for(i = 1; i <= lgrez; ++i){
        for(j = 0; j< Rez[i].size(); ++j)
            fout<<Rez[i][j]<<" ";
        fout<<'\n';
    }

    return 0;
}

void init(){
    int x, y, i;
    fin>>n>>m;
    for(i = 0;i < m;i++){
        fin>>x>>y;
        A[x].push_back(y);
        At[y].push_back(x);
    }
}



void DFS1(int k){
    int i;
    uz[k] = 1;
    for(i = 0; i< A[k].size(); ++i)
        if(!uz[A[k][i]])
            DFS1(A[k][i]);
    postordine[++nr] = k;
}

void DFST(int k){
    int i;
    uz2[k] = 1;
    Rez[lgrez].push_back(k);
    for(i = 0; i< At[k].size(); ++i){
        if(!uz2[At[k][i]]){
            DFST( At[k][i] );
        }
    }
}