Cod sursa(job #1013212)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 20 octombrie 2013 16:33:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using std::vector;
using std::list;
using std::stack;

void getBcc(list<list<unsigned> > &bccl, unsigned n, vector<list<unsigned> > &Adj){
    vector<unsigned> index(n+1,0), lowlink(n+1,n+2);

    for(unsigned ri=1;ri<=n;++ri) if(index[ri]==0){   //for each (1-)connected component
        index[ri]=lowlink[ri]=1;
        stack<unsigned> dfst;
        stack<unsigned> ccst;

        dfst.push(ri); ccst.push(ri);
        while(!dfst.empty()){
            bool pop=true;
            unsigned u=dfst.top();

            for(;!Adj[u].empty()&&pop;Adj[u].pop_front()){
                unsigned v=Adj[u].front();
                if(index[v]==0){   //new node occured
                    pop=false;
                    dfst.push(v);
                    index[v]=lowlink[v]=index[u]+1;
                }
                else{   //returning edge
                    if(index[v]<lowlink[u]) lowlink[u]=index[v];
                }
            }

            if(pop){
                dfst.pop();

                if(lowlink[u]==index[u]-1){  //u's parent is the root of a bcc
                    bccl.push_back(list<unsigned>());
                    bccl.back().push_back(dfst.top());
                    bccl.back().push_back(u);
                    while(!ccst.empty()&&index[ccst.top()]>index[u]){
                        bccl.back().push_back(ccst.top());
                        ccst.pop();
                    }
                }
                else ccst.push(u);
                if(!dfst.empty()) if(lowlink[dfst.top()]>lowlink[u]) lowlink[dfst.top()]=lowlink[u];
            }
        }
    }
}

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

    unsigned n,m;
    fin>>n>>m;

    vector< list<unsigned> > Adj(n+1);   //nodes are numbered from 1 to n

    for(unsigned i=0;i<m;++i){   //reading edges
        unsigned x,y;
        fin>>x>>y;
        Adj[x].push_back(y);
        Adj[y].push_back(x);
    }

    list< list<unsigned> > bccl;   //list of biconnected components

    getBcc(bccl,n,Adj);

    fout<<bccl.size()<<'\n';
    for(auto i=bccl.begin();i!=bccl.end();++i){   //write each component to the file
        for(auto j=i->begin();j!=i->end();++j) fout<<*j<<' ';
        fout<<'\n';
    }
}