Pagini recente » Cod sursa (job #844026) | Cod sursa (job #1905489) | Cod sursa (job #1615996) | Cod sursa (job #3238834) | Cod sursa (job #2472107)
#include<fstream>
#include<vector>
using namespace std;
#define maxn 100005
vector <int> v[maxn],c[maxn],stk;
int low[maxn],dfn[maxn],n,m,cnt;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
void read(){
cin>>n>>m;
int x,y;
while(m){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
m--;
}
}
void clear_stk(int x, int y){
int x1,y1;
cnt++;
y1=stk.back(); stk.pop_back();
x1=stk.back(); stk.pop_back();
c[cnt].push_back(y1);
c[cnt].push_back(x1);
while(x!=x1||y!=y1){
y1=stk.back(); stk.pop_back();
x1=stk.back(); stk.pop_back();
if(y1!=c[cnt].back())
c[cnt].push_back(y1);
c[cnt].push_back(x1);
}
}
void dfs(int n, int fn, int number){
vector<int>::iterator it;
dfn[n]=low[n]=number;
for(it=v[n].begin(); it!=v[n].end(); it++){
if(*it==fn)
continue;
else if(!dfn[*it]){
stk.push_back(n);
stk.push_back(*it);
dfs(*it, n, ++number);
low[n]=min(low[*it],low[n]);
if(dfn[n]<=low[*it])
clear_stk(n,*it);
}
else
low[n]=min(low[n],low[*it]);
}
}
void solve(){
dfs(1,-1,1);
cout<<cnt<<'\n';
for(int i=1; i<=cnt; i++){
for(vector <int>::iterator it=c[i].end()-1; it>=c[i].begin(); it--)
cout<<*it<<' ';
cout<<'\n';
}
}
int main(){
read();
solve();
return 0;
}