Cod sursa(job #943108)

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

#define MAX 100000
#define MAX_comp 4000

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;

void dfs1(int nod ,int (&viz)[MAX]){

    viz[nod]=1;

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

    s.push(nod);

}

void dfs2(int nod, int (&viz)[MAX]){

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

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

}

void tarjan( int (&viz)[MAX] ){

    int val;

    while(!s.empty()){

        val=s.top();
        cout<<val<<" ";
        s.pop();
        if(viz[val]==0){
            dfs2(val,viz);
            nr_comp_conexe++;
        }

    }

}

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,viz[MAX],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++)
        viz[i]=0;

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

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

    tarjan(viz);


    afisare();

    return 0;
}