Pagini recente » Cod sursa (job #556934) | Cod sursa (job #2237612) | Cod sursa (job #473178) | Cod sursa (job #1214101) | Cod sursa (job #585422)
Cod sursa(job #585422)
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define NMAX 100006
#define minim(a,b) (a<b ? a : b)
stack<pii > st;
vector<vector<pii > > sol;
vector<int> v[NMAX];
int n,m,cnt;
int viz[NMAX];
int up[NMAX],dep[NMAX],h[NMAX];
void dfs(int nod)
{
int i,vec,lim=v[nod].size();
viz[nod]=1;
dep[nod]=h[nod];
for(i=0;i<lim;i++)
if(!viz[vec=v[nod][i]])
{
h[vec]=h[nod]+1;
up[vec]=nod;
st.push(mp(nod,vec));
dfs(vec);
if (dep[vec] >= h[nod])
{
sol.pb(vector<pii>());
while (st.top()!=mp(nod,vec))
{
sol[cnt].pb(st.top());
st.pop();
}
sol[cnt].pb(st.top());
st.pop();
++cnt;
}
dep[nod]=minim(dep[nod],dep[vec]);
}
else if (vec!=up[nod])
dep[nod]=minim(dep[nod],h[vec]);
}
int main ()
{
int i,j,lim,a,b;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
v[a].pb(b);
v[b].pb(a);
}
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
memset(viz,0,sizeof(viz));
printf("%d\n", cnt);
for(i=0;i<cnt;i++)
{
lim=sol[i].size();
for(j=0;j<lim;j++)
{
if(viz[a=sol[i][j].first]!=i+1)
{
printf("%d ", a);
viz[a]=i+1;
}
if(viz[a=sol[i][j].second]!=i+1)
{
printf("%d ", a);
viz[a]=i+1;
}
}
printf("\n");
}
return 0;
}