Pagini recente » Cod sursa (job #2501964) | Cod sursa (job #1544446) | Cod sursa (job #746706) | Cod sursa (job #1281552) | Cod sursa (job #1851336)
#include<cstdio>
#include<vector>
using namespace std;
struct eu{int x,y;};
eu st[200001];
vector<int> v[100001],v1[100001];
int cate,i,n,j,m,nr,cate2,pc,viz[100001],niv[100001],l[100001],marc[100001],tata[1000001],vc[100001],x,y,rad,cc;
void pas(int x,int y)
{
int q1=st[cate].x,q2=st[cate].y;
cate--;
cate2++;
while(x!=q1&&y!=q2)
{
v1[cate2].push_back(q1);
v1[cate2].push_back(q2);
q1=st[cate].x;
q2=st[cate].y;
cate--;
}
v1[cate2].push_back(q1);
v1[cate2].push_back(q2);
}
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];
}
else
{
st[++cate].x=nod;
st[cate].y=f;
if(nod==rad)
nr++;
niv[f]=niv[nod]+1;
tata[f]=nod;
dfs(f);
if(l[nod]>l[f])
l[nod]=l[f];
if(l[f]>=niv[nod])
{
marc[nod]=1;
pas(nod,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;
vc[++cc]=i;
nr=0;
dfs(i);
if(nr>=2)
marc[i]=1;
else
marc[i]=0;
}
printf("%d\n",cate2);
for(i=1;i<=cate2;i++)
{
for(j=v1[i].size()-1;j>=0;j-=2)
printf("%d ",v1[i][j]);
printf("%d\n",v1[i][v1[i].size()-2]);
}
return 0;
}