Pagini recente » Cod sursa (job #1389923) | Cod sursa (job #2249695) | Cod sursa (job #2787896) | Cod sursa (job #2552416) | Cod sursa (job #431562)
Cod sursa(job #431562)
#include<stdio.h>
#define Nmax 100010
#define Mmax 200010
struct nod
{
int inf;
nod *urm;
}*a[Nmax],*s[Nmax];
int niv[Nmax],nivmin[Nmax],cr[Nmax],ncr,t[Nmax],pam[Nmax];
int n,m,viz[Nmax];
int sol[Mmax][2],nr;
void listare(int a1,int b1,int &poz)
{
nod *p;
if(pam[sol[poz][0]]!=ncr)
{ p=new nod;
p->inf=sol[poz][0];
p->urm=s[ncr];
s[ncr]=p;
pam[sol[poz][0]]=ncr;
}
if(pam[sol[poz][1]]!=ncr)
{ p=new nod;
p->inf=sol[poz][1];
p->urm=s[ncr];
s[ncr]=p;
pam[sol[poz][1]]=ncr;
}
if(!((sol[poz][0]==a1 && sol[poz][1]==b1) || (sol[poz][1]==a1 && sol[poz][0]==b1)))
{
poz--;
listare(a1,b1,poz);
}
}
void DF(int x)
{
nod *p;
for(p=a[x];p!=NULL;p=p->urm)
{
if( t[x]!=p->inf)
{
if(viz[p->inf]!=0)
{
if(niv[p->inf]<nivmin[x])
nivmin[x]=niv[p->inf];
}
else
{
t[p->inf]=x;
viz[p->inf]=viz[x];
niv[p->inf]=niv[x]+1;
nivmin[p->inf]=niv[p->inf];
nr++;
sol[nr][0]=x;
sol[nr][1]=p->inf;
DF(p->inf);
if(nivmin[p->inf]<nivmin[x])
nivmin[x]=nivmin[p->inf];
if(nivmin[p->inf]>=niv[x])
{
ncr++;
listare(x,p->inf,nr);
nr--;
}
}
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
int i,x,y;
nod *p;
nr--;
for(i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
p=new nod;
p->inf=y;
p->urm=a[x];
a[x]=p;
p=new nod;
p->inf=x;
p->urm=a[y];
a[y]=p;
}
niv[1]=1;
viz[1]=1;
nivmin[1]=1;
t[1]=1;
DF(1);
/*int ok=0;
if(nr>=0)
{listare(sol[0][0],sol[0][1],nr);
ok=1;}
if(ok)
else
printf("%d\n",ncr-1);*/
printf("%d\n",ncr);
for(i=1;i<=ncr;i++)
{
for(p=s[i];p!=NULL;p=p->urm)
printf("%d ",p->inf);
printf("\n");
}
return 0;
}