Pagini recente » Cod sursa (job #1241010) | Cod sursa (job #589872) | Cod sursa (job #742595) | Cod sursa (job #93036) | Cod sursa (job #1607588)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100010
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int low[nmax];
vector<int> dfn(nmax,-1);
vector <int> V[nmax];
vector < vector < int > > Sol;
stack < pair <int , int > > S;
vector <int> M;
int n,m;
void read(){
f>>n>>m;
int x,y;
for(int i=0;i<m;++i){
f>>x>>y;
V[x].push_back(y);
V[y].push_back(x);
}
}
void salveaza(int a,int b){
int xi,yi;
do{
xi=S.top().first;
yi=S.top().second;
S.pop();
M.push_back(xi);
M.push_back(yi);
}while(xi!=a || yi!=b );
sort(M.begin(),M.end());
M.erase(unique(M.begin(),M.end()),M.end());
Sol.push_back(M);
M.clear();
}
void biconex(int x,int xt,int num){
dfn[x]=low[x]=num;
for(vector<int>::iterator it=V[x].begin();it!=V[x].end();++it){
if(xt==*it) continue;
if(dfn[*it]==-1){
S.push(make_pair(x,*it));
biconex(*it,x,num+1);
low[x]=min(low[x],low[*it]);
if(low[*it]>=dfn[x]){
salveaza(x,*it);
}
}else{
low[x]=min(low[x],dfn[*it]);
}
}
}
int main()
{
read();
biconex(1,0,1);
g<<Sol.size()<<"\n";
for(int i=0;i<Sol.size();i++){
for(int j=0;j<Sol[i].size();j++){
g<<Sol[i][j]<<" ";
}g<<"\n";
}
return 0;
}