Cod sursa(job #996720)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 12 septembrie 2013 15:54:07
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <stack>

typedef std::list< std::list<unsigned> > LLU_t;
typedef std::vector< std::queue<unsigned> > VQU_t;

void tarjan(LLU_t &scc, unsigned N, VQU_t &Adj){
    std::stack<unsigned> TarjanStack, DfsStack;
    std::vector<bool> instack(N+1,false);
    std::vector<unsigned> index(N+1,0);
    std::vector<unsigned> lowlink(N+1,0);
    unsigned cind=1;

    for(unsigned k=1;k<=N;++k) if(index[k]==0){
        DfsStack.push(k);
        while(!DfsStack.empty()){
            unsigned &v=DfsStack.top();
            if(index[v]==0){
                TarjanStack.push(v); instack[v]=true;
                index[v]=cind;
                lowlink[v]=cind;
                ++cind;
            }

            bool cont=true;
            while(!Adj[v].empty()&&cont){
                if(index[Adj[v].front()]==0){
                    DfsStack.push(Adj[v].front());
                    cont=false;
                }
                else if(instack[Adj[v].front()]&&lowlink[v]>lowlink[Adj[v].front()])
                    lowlink[v]=lowlink[Adj[v].front()];

                if (cont) Adj[v].pop();
            }

            if(!cont) continue;
            if(lowlink[v]==index[v]){
                std::list<unsigned> temp;
                do{
                    temp.push_front(TarjanStack.top());
                    instack[TarjanStack.top()]=false;
                    TarjanStack.pop();
                }while(temp.front()!=v);
                scc.push_back(temp);
            }
            DfsStack.pop();
        }
    }
}

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

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

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