Pagini recente » Cod sursa (job #1714007) | Cod sursa (job #1732067) | Cod sursa (job #2681296) | Cod sursa (job #1276223) | Cod sursa (job #473496)
Cod sursa(job #473496)
#include <vector>
#include <cstdio>
#include <stack>
#define N 100001
#define INF 0x7fffffff
using namespace std;
vector<int> g[N];
vector<stack<int> >r;
stack<int> st;
int depth[N];
int reach[N];
void df(int k,int t,int d)
{int i;
st.push(k);
depth[k]=d;
reach[k]=d;
for (i=0;i<g[k].size();i++)
{if(g[k][i]==t)continue;
if(depth[g[k][i]]==-1)
{df(g[k][i],k,d+1);
if(reach[g[k][i]]>=d)
{stack<int> s;
while(st.top()!=k)
{s.push(st.top());
st.pop();
}
s.push(st.top());
r.push_back(s);
}
else
{if(reach[k]>reach[g[k][i]])
{reach[k]=reach[g[k][i]];
}
}
}
else
{if(reach[k]>reach[g[k][i]])
{reach[k]=reach[g[k][i]];
}
}
}
}
int main ()
{freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m,i,x,y;
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++)
{scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for (i=1;i<=n;i++)
{depth[i]=-1;
reach[i]=INF;
}
df(1,0,0);
// for (i=1;i<=n;i++) {printf("%d %d %d\n",i,depth[i],reach[i]);}
printf("%d\n",r.size());
for (int i=0;i<r.size();i++)
{while(!r[i].empty())
{printf("%d ",r[i].top());
r[i].pop();
}
printf("\n");
}
return 0;
}