Pagini recente » Cod sursa (job #36024) | Cod sursa (job #2330826) | Cod sursa (job #691132) | Cod sursa (job #2474157) | Cod sursa (job #574062)
Cod sursa(job #574062)
#include<cstdio>
using namespace std;
typedef struct nod
{
int inf;
nod *urm;
} NOD;
typedef NOD *graf[100010];
graf G;
graf sol;
FILE *f;
FILE *g;
int n,m,niv[100010],nivm[100010],viz[100010],t[100010],q[200010],ind=1,nrsol;
void citire()
{
f=fopen("biconex.in","r");
fscanf(f,"%d %d",&n, &m);
int x,y;
NOD *p;
for(int i=1;i<=m;i++)
{
fscanf(f,"%d %d",&x,&y);
p=new NOD; p->inf=y; p->urm=G[x]; G[x]=p;
p=new NOD; p->inf=x; p->urm=G[y]; G[y]=p;
}
}
void regulate()
{
for(int i=1;i<=n;i++)
if(viz[i])
viz[i]=1;
}
void compon(int x, int y)
{
nrsol++;
int a,b;
NOD *p;
do
{
a=q[ind-1];b=q[ind-2];
p=new NOD;
p->inf=a;p->urm=sol[nrsol];sol[nrsol]=p;
p=new NOD;
p->inf=b;p->urm=sol[nrsol];sol[nrsol]=p;
ind-=2;
} while(a!=y||b!=x);
}
void DF(int k, int nivel)
{
niv[k]=nivm[k]=nivel;
NOD *p;
p=G[k];viz[k]=1;
while(p)
{
if(p->inf!=t[k])
{
if(!viz[p->inf])
{
q[ind++]=k;q[ind++]=p->inf;
t[p->inf]=k;
DF(p->inf,nivel+1);
if(nivm[p->inf]>=niv[k])
compon(k,p->inf);
if(nivm[k]>nivm[p->inf])
nivm[k]=nivm[p->inf];
}
else
if(nivm[k]>nivm[p->inf])
nivm[k]=nivm[p->inf];
}
p=p->urm;
}
}
void afis()
{
g=fopen("biconex.out","w");
fprintf(g,"%d\n",nrsol);
for(int i=1;i<=nrsol;i++)
{
NOD *p;
p=sol[i];
while(p)
{
viz[p->inf]=0;
p=p->urm;
}
p=sol[i];
while(p)
{
if(!viz[p->inf])
{
fprintf(g,"%d ",p->inf);
viz[p->inf]=1;
}
p=p->urm;
}
fprintf(g,"\n");
}
}
int main()
{
citire();
DF(1,1);
afis();
return 0;
}