Cod sursa(job #943112)

Utilizator Pcosmin93Posteuca Cosmin Pcosmin93 Data 24 aprilie 2013 12:44:23
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<stack>

#define MAX 100000

using namespace std;

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

vector <int> graf1[MAX],graf2[MAX],comp_conexe[MAX];
stack <int> s;
int nr_comp_conexe,viz[MAX];

void dfs1(int nod ){

    viz[nod]=1;

    for( unsigned int i = 0 ; i < graf1[nod].size(); i++ )
        if(viz[graf1[nod][i]]==0)
            dfs1(graf1[nod][i]);

    s.push(nod);

}

void dfs2(int nod){

    viz[nod]=0;
    comp_conexe[nr_comp_conexe].push_back(nod);

    for(unsigned int i = 0 ; i < graf2[nod].size() ; i++ )
        if(viz[graf2[nod][i]]==1)
            dfs2(graf2[nod][i]);

}

void tarjan( ){

    int val;

    while(!s.empty()){


        if(viz[s.top()]==1){
            dfs2(s.top());
            nr_comp_conexe++;
        }

        s.pop();

    }

}

void afisare(){

    unsigned int i;
    int j;

    out<<nr_comp_conexe<<endl;

    for( j = 0 ; j < nr_comp_conexe ; j++ ){
        for( i = 0; i < comp_conexe[j].size(); i++)
            out<<comp_conexe[j][i]<<" ";
        out<<endl;
    }
}


int main(){

    int n,m,x,y,i;

    in>>n>>m;

    for( i = 1; i <= m; i++){

        in>>x>>y;
        graf1[x].push_back(y);
        graf2[y].push_back(x);

    }

    for(i = 1 ; i <= n ; i++ )
        if(viz[i]==0)
            dfs1(i);


    tarjan();

    afisare();

    return 0;
}