Cod sursa(job #1251342)

Utilizator ioanaandraciobanuIoana Andra Ciobanu ioanaandraciobanu Data 29 octombrie 2014 12:24:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#define dmax 100005

using namespace std;

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

int n, m, ct, poz_postord, uz[dmax],postord[dmax];
vector <int> grf[dmax];
vector <int> grft[dmax];
vector <int> sol[dmax];

void citire();
void rezolvare();
void dfs1(int );
void dfs2(int );
void afisare();

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

void citire(){
    int x, y;
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        fin>>x>>y;
        grf[x].push_back(y);
        grft[y].push_back(x);
    }
}

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

void dfs1(int vf){
    uz[vf]=1;
    for(int i=0; i<grf[vf].size(); ++i)
        if(!uz[grf[vf][i]])
            dfs1(grf[vf][i]);
    postord[++poz_postord]=vf;
}

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

void afisare(){
    int i, j;
    fout<<ct<<'\n';
    for(i=1; i<=ct; ++i){
        for(j=0; j<sol[i].size(); ++j)
            fout<<sol[i][j]<<" ";
        fout<<'\n';
    }
}