Cod sursa(job #996760)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 12 septembrie 2013 16:22:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using std::stack;
using std::vector;
using std::list;

void strongconnect(unsigned v, unsigned &cind, stack<unsigned> &S,
                   vector<unsigned> &index, vector<unsigned> &lowlink, vector<bool> &instack,
                   list< list<unsigned> > &scc,
                   unsigned N, const vector< list<unsigned> > &Adj){
    index[v]=lowlink[v]=cind++;
    S.push(v); instack[v]=true;

    for(list<unsigned>::const_iterator w=Adj[v].begin();w!=Adj[v].end();++w){
        if(index[*w]==0){
            strongconnect(*w,cind,S,index,lowlink,instack,scc,N,Adj);
            if(lowlink[v]>lowlink[*w]) lowlink[v]=lowlink[*w];
        }
        else if(instack[*w]&&lowlink[v]>index[*w]) lowlink[v]=index[*w];
    }

    if(lowlink[v]==index[v]){
        list<unsigned> temp;
        unsigned w;
        do{
            w=S.top(); S.pop(); instack[w]=false;
            temp.push_back(w);
        }while(w!=v);
        scc.push_back(temp);
    }
}

int main(){
    std::ifstream fin("ctc.in");
    std::ofstream fout("ctc.out");

    unsigned N,M;
    fin>>N>>M;
    vector< list<unsigned> > Adj(N+1);
    for(unsigned i=0;i<M;++i){unsigned x,y; fin>>x>>y; Adj[x].push_back(y);}

    list< list<unsigned> > scc;

    unsigned cind=1;
    stack<unsigned> S;
    vector<unsigned> index(N+1,0);
    vector<unsigned> lowlink(N+1,0);
    vector<bool> instack(N+1,0);

    for(unsigned i=1;i<=N;++i)
        if(index[i]==0) strongconnect(i,cind,S,index,lowlink,instack,scc,N,Adj);

    fout<<scc.size()<<'\n';
    for(list<list<unsigned> >::iterator i=scc.begin();i!=scc.end();++i){
        for(list<unsigned>::iterator j=i->begin();j!=i->end();++j) fout<<*j<<' ';
        fout<<'\n';
    }
}