Cod sursa(job #896783)

Utilizator denisa29Denisa Patricia denisa29 Data 27 februarie 2013 17:14:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct graf
{int info; graf *urm;};
graf *a[100001],*sol[100001];
int n,m,cont,niv[100001],nivmin[100001],viz[100001],sx[200001],sy[200001],prim,pa[100001];


void adauga_nod(int x,int y)
{graf *p=new graf;
p->info=y; p->urm=a[x]; a[x]=p;
}

void adauga_sol(int x,int y)
{{graf *p=new graf;
p->info=y; p->urm=sol[x]; sol[x]=p;
}

}

void adauga(int x, int y)
{int nr=0,i,j;
cont++;
i=sx[prim]; j=sy[prim]; prim--;
nr++;
adauga_sol(cont,j);
while(i!=x || j!=y)
    {i=sx[prim]; j=sy[prim]; prim--;
    nr++;
    adauga_sol(cont,j);
    }
nr++;
adauga_sol(cont,i);
}

void DF(int nod, int tata)
{int x;
 graf *p;
niv[nod]=niv[tata]+1;
nivmin[nod]=niv[nod];
viz[nod]=1;
for(p=a[nod];p!=NULL;p=p->urm)
    {x=p->info;
    if(!viz[x])
        {prim++; sx[prim]=nod; sy[prim]=x;
        DF(x,nod);
        if(nivmin[x]<nivmin[nod])
            nivmin[nod]=nivmin[x];
        if(nivmin[x]>=niv[nod])
            adauga(nod,x);
        }
     else if(x!=tata && nivmin[x]<nivmin[nod])
            nivmin[nod]=nivmin[x];
    }

}


int main()
{int i,j,x;
graf *p;
fin>>n>>m;
for(i=1;i<=n;i++)
    {a[i]=NULL;
    niv[i]=0; nivmin[i]=0; viz[i]=0; pa[i]=0;
    }
for(x=1;x<=m;x++)
    {fin>>i>>j; adauga_nod(i,j); adauga_nod(j,i);}
prim=0;
DF(1,0);
fout<<cont<<endl;
for(i=1;i<=cont;i++)
    {for(p=sol[i];p!=NULL;p=p->urm)
        fout<<p->info<<" ";
    fout<<endl;
    }
}