Pagini recente » Cod sursa (job #508338) | Cod sursa (job #189283) | Cod sursa (job #2527803) | Cod sursa (job #447210) | Cod sursa (job #1155365)
#include<fstream>
using namespace std;
struct nod{int info ;
nod * urm;}v[100001],*p,*w[100001];
int x,y,u,cc[200001],poz[100001],poz2[100001],c[100001],ccc[100001],u2,pozc[100001];
void df(int x,int y)
{
nod *q;
q=&v[x];
ccc[++u2]=x;
pozc[x]=u2;
while(q->urm!=NULL)
{
if(poz[q->urm->info]!=0){if(q->urm->info!=y&&c[q->urm->info]==0)c[x]=q->urm->info;}
else {poz[q->urm->info]=x;
df(q->urm->info,x);}
if(q!=NULL)q=q->urm;
if(q==NULL)break;
}
}
void conex()
{int x2,y2;
if(y!=c[ccc[x]])
{
cc[++u]=y;
poz2[y]=1;
y=poz[y];
}
while(y!=c[ccc[x]])
{
cc[++u]=y;
if(c[y]!=0)
{
x2=x;y2=y;
x=pozc[y];y=c[x];
conex();
x=x2;y=y2;
}
poz2[y]=1;
y=poz[y];
}
if(poz2[y]==0)
{
cc[++u]=y;
cc[++u]=-1;
}
}
int main()
{
int n,m,i,k=0;
ifstream fcin("biconex.in");
ofstream fcout("biconex.out");
fcin>>n>>m;
for(i=1;i<100001;i++)
{v[i].info=0;v[i].urm=NULL;w[i]=&v[i];}
for(i=1;i<=m;i++)
{ fcin>>x>>y;
v[x].info++;
p=new nod;
p->info=y;
p->urm=NULL;
w[x]->urm=p;
w[x]=p;
v[y].info++;
p=new nod;
p->info=x;
p->urm=NULL;
w[y]->urm=p;
w[y]=p;
}
poz[1]=-1;
df(1,-1);
x=u2;
while(x!=1)
{
if(poz2[ccc[x]]==0)
{
if(c[ccc[x]]!=0)
{y=ccc[x];k++;
conex();
/*while(y!=c[ccc[x]])
{cc[++u]=y;
poz2[y]=1;
y=poz[y];}
cc[++u]=y;
cc[++u]=-1;*/
}
else {k++;cc[++u]=ccc[x];poz2[ccc[x]]=1;cc[++u]=poz[ccc[x]];cc[++u]=-1;}
}
x--;
}
fcout<<k<<'\n';
u=1;
while(k!=0)
{
while(cc[u]!=-1)
{fcout<<cc[u]<<' ';u++;}
fcout<<'\n';u++;
k--;
}
return 0;
}