Pagini recente » Cod sursa (job #1732706) | Cod sursa (job #2678413) | Cod sursa (job #366140) | Cod sursa (job #1527434) | Cod sursa (job #1013212)
#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';
}
}