Pagini recente » Cod sursa (job #2936718) | Cod sursa (job #2025083) | Cod sursa (job #2271198) | Cod sursa (job #3230768) | Cod sursa (job #574018)
Cod sursa(job #574018)
#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)
{
nrsol++;
int i;
for(i=1;i<=x&&!q[i];i++)
;
NOD *p;
p=sol[nrsol];
for(;i<=x;i++)
{
p=new NOD;
if(viz[q[i]]==1)
{
viz[q[i]]++;
p->inf=q[i];p->urm=sol[nrsol];sol[nrsol]=p;
}
q[i]=0;
}
}
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;
int iaux=ind;
t[p->inf]=k;
DF(p->inf,nivel+1);
if(nivm[p->inf]>=niv[k])
compon(iaux-2);
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)
{
fprintf(g,"%d ",p->inf);
p=p->urm;
}
fprintf(g,"\n");
}
}
int main()
{
citire();
DF(1,1);
afis();
return 0;
}