Pagini recente » Cod sursa (job #738506) | Istoria paginii runda/aisimlocala | Cod sursa (job #2301929) | Cod sursa (job #1889950) | Cod sursa (job #2238297)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int NMAX=100005;
int g=0,cnt;
int rootChildren,dfsRoot;
struct muchie{
int u,v;
}aux;
vector <int> G[NMAX];
vector <int> sol[NMAX];
int idx[NMAX],low[NMAX],parent[NMAX];
int ap[NMAX];
stack <muchie> st;
void dfs(int u){
++g;
idx[u]=low[u]=g;
for(int i=0; i<G[u].size(); ++i){
int v=G[u][i];
if(idx[v]==0){
aux.u=u;
aux.v=v;
st.push(aux);
parent[v]=u;
dfs(v);
if(low[v]>=idx[u]){
ap[u]=1;
cnt++;
while(st.top().u!=u || st.top().v!=v){
sol[cnt].push_back(st.top().v);
st.pop();
}
sol[cnt].push_back(u);
}
low[u]=min(low[v],low[u]);
}
else{
if(v!=parent[u]){
low[u]=min(low[u],idx[v]);
}
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m;
int u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;++i){
if(idx[i]==0){
dfsRoot=i; rootChildren=0;
dfs(i);
if(rootChildren>1){
while(!st.empty()){
sol[cnt].push_back(st.top().u);
st.pop();
}
sol[cnt].push_back(i);
}
else
ap[i]=0;
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i){
for(int j=sol[i].size()-1;j>=0;--j)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}