Cod sursa(job #1124462)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 26 februarie 2014 12:26:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<vector>
#define dim 100005
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
int ctc,n,m,i,j,st[dim],Mark[dim],viz[dim],x,y,k;
vector<int>T[dim],G[dim],sol[dim];
void dfp(int nod) {
    viz[nod]=1;

    for(int i=0;i<G[nod].size();++i){
        int fiu=G[nod][i];
        if(!viz[fiu])
            dfp(fiu);
    }
    st[++k]=nod;
}
void dfm( int nod ,int ctc){

    Mark[nod]=ctc;

    for(int i=0;i<T[nod].size();++i){

        int fiu=T[nod][i];

        if(!Mark[fiu]){
             sol[ctc].push_back(fiu);
            dfm(fiu,ctc);

        }
    }
}
int main () {

    f>>n>>m;

    for(i=1;i<=m;++i){
        f>>x>>y;
        G[x].push_back(y);
        T[y].push_back(x);
    }
    for(i=1;i<=n;i++) {
        if(!viz[i])
            dfp(i);
    }
    for(;k;st[k--]=0){

        if(Mark[st[k]]==0) {
            sol[++ctc].push_back(st[k]);
            dfm(st[k],ctc);
        }
    }
    g<<ctc<<"\n";
    for(i=1;i<=ctc;++i){
            for(j=0;j<sol[i].size();++j){
                g<<sol[i][j]<<" ";
            }
            g<<"\n";

    }
    return 0;
}