Pagini recente » Cod sursa (job #519788) | Cod sursa (job #900916)
Cod sursa(job #900916)
#include<stdio.h>
#include<vector>
#include<stack>
#define maxn 100003
using namespace std;
int n,m,nrb,t[maxn],v[maxn],nv[maxn],nr;
vector <int> l[maxn],r[maxn];
stack <int> s;
void cit()
{
int i;
scanf("%d %d",&n,&m);
int x,y;
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
l[x].push_back(y);
l[y].push_back(x);
}
}
void go(int x,int y)
{
nrb++;
while(s.top()!=y)
{
r[nrb].push_back(s.top());
s.pop();
}
r[nrb].push_back(x);
r[nrb].push_back(y);
s.pop();
}
int df(int k,int niv)
{
int i,nr,nvad,minn;
s.push(k); v[k]=1; nv[k]=niv; minn=niv;
nr=l[k].size();
for(i=0;i<nr;i++)
if(v[l[k][i]]==0)
{
t[l[k][i]]=k;
nvad=df(l[k][i],niv+1);
if(minn>nvad)
minn=nvad;
if(niv<=nvad)
go(k,l[k][i]);
}
else
if(minn>nv[l[k][i]] && l[k][i]!=t[k])
minn=nv[l[k][i]];
return minn;
}
void afis()
{
int i,nr,j;
printf("%d\n",nrb);
for(i=1;i<=nrb;i++)
{
nr=r[i].size();
for(j=0;j<nr;j++)
printf("%d ",r[i][j]);
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
cit();
nr=df(1,1);
afis();
fclose(stdin);
fclose(stdout);
return 0;
}