Pagini recente » Cod sursa (job #1806592) | Cod sursa (job #1907908) | Cod sursa (job #1938289) | Cod sursa (job #1748806) | Cod sursa (job #1847075)
#include<cstdio>
#include<vector>
using namespace std;
struct eu{int x,y;};
eu st[200001];
vector<int> v[100001],vcc[200001];
int i,n,j,q1,m,nr,pc,cate,da,viz[100001],niv[100001],l[100001],tata[1000001],x,y,rad,cc;
void dfs(int nod)
{
viz[nod]=1;
l[nod]=niv[nod];
for(int i=0;i<v[nod].size();i++)
{
int f=v[nod][i];
if(viz[f]==1)
{
if(f!=tata[nod]&&l[nod]>niv[f])
{
l[nod]=niv[f];
int ops=cate,hh=0,h=0;
while(st[ops].y!=nod&&ops>0)
{
ops--;
hh++;
}
if(ops>0)
{
vcc[q1].push_back(st[ops].y);
while(st[ops].x!=f&&ops>0)
{
vcc[q1].push_back(st[ops].x);
ops--;
h++;
}
if(ops>0)
{
q1++;
vcc[q1].push_back(f);
ops--;
h++;
for(int a=1;a<=hh;a++)
st[ops+a]=st[ops+h+a];
cate-=h;
da=f;
}
}
}
}
else
{
if(nod==rad)
nr++;
niv[f]=niv[nod]+1;
st[++cate].x=nod;
st[cate].y=f;
while(cate>=2&&st[cate].x!=st[cate-1].y&&st[cate-1].y!=da)
{
int kappa=cate-1,l=0;
while(st[kappa].y!=st[cate].x&&st[kappa].y!=da)
{
q1++;
vcc[q1].push_back(st[kappa].x);
vcc[q1].push_back(st[kappa].y);
kappa--;
l++;
}
st[cate-l]=st[cate];
cate-=l;
}
tata[f]=nod;
dfs(f);
if(l[nod]>l[f])
l[nod]=l[f];
}
}
}
int main ()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1;i<=n;i++)
if(viz[i]==0)
{
rad=i;
niv[i]=1;
nr=0;
dfs(i);
}
printf("%d\n",q1+cate);
for(int i=1;i<=q1;i++)
{
for(j=0;j<vcc[i].size();j++)
printf("%d ",vcc[i][j]);
printf("\n");
}
for(int i=1;i<=cate;i++)
{
printf("%d %d",st[i].x,st[i].y);
printf("\n");
}
return 0;
}