Pagini recente » Cod sursa (job #1357097) | Cod sursa (job #1575558) | Cod sursa (job #1864743) | Cod sursa (job #1505140) | Cod sursa (job #555552)
Cod sursa(job #555552)
#include<fstream>
using namespace std;
int n,m,dfn[100005],low[100005],con[100005],contor;
typedef
struct nod
{
int nr;
nod *urm;
}*Pnod;
typedef
struct stiva
{
int a,b;
stiva*urm;
}*Pstiva;
Pnod l[100005],sol[100005];
Pstiva st[100005],vf;
ofstream fout("biconex.out");
void quick(int inf, int sup)
{
if(inf<sup)
{
int pivot=con[inf],aux;
int i=inf+1,j=sup;
while(i<=j)
{
while(i<=sup&&con[i]<=pivot)
i++;
while(j>=inf&&con[j]>pivot)
j--;
if(i<j&&i<=sup&&j>=inf)
{aux=con[i];
con[i]=con[j];
con[j]=aux;
i++;
j--;
}
}
i--;
con[inf]=con[i];
con[i]=pivot;
quick(inf,i-1);
quick(i+1,sup);
}
}
void componenta(int x, int y)
{
int tx=0,ty=0,sw=0,i;
contor++;
Pnod q;
con[0]=0;
while(sw!=2)
{
con[0]++;
/*q=new(nod);
q->nr=vf->a;
q->urm=sol[contor];
sol[contor]=q;*/
con[con[0]]=vf->a;
if(vf->a==x&&tx==0)
tx++;
else if(vf->a==y&&ty==0)
ty++;
con[0]++;
/*q=new(nod);
q->nr=vf->b;
q->urm=sol[contor];
sol[contor]=q;*/
con[con[0]]=vf->b;
if(vf->b==x&&tx==0)
tx++;
else if(vf->b==y&&ty==0)
ty++;;
vf=vf->urm;
sw=tx+ty;
}
//fout<<con[0]<<endl;
quick(1,con[0]);
int val;
i=1;
while(i<=con[0])
{
val=con[i];
q=new(nod);
q->nr=con[i];
q->urm=sol[contor];
sol[contor]=q;
i++;
while(con[i]==val)
i++;
//fout<<con[contor][i]<<" ";
}
}
void df(int n,int fn,int nivel)
{
Pnod p;
Pstiva r;
dfn[n]=low[n]=nivel;
for(p=l[n];p!=NULL;p=p->urm)
if(p->nr!=fn)
if(dfn[p->nr]==-1)
{
r=new(stiva);
r->a=n;
r->b=p->nr;
r->urm=vf;
vf=r;
df(p->nr,n,nivel+1);
if(low[n]>low[p->nr])
low[n]=low[p->nr];
if(low[p->nr]>=dfn[n])
componenta(n,p->nr);
//fout<<n<<" ";
}
else
if(low[n]>low[p->nr])
low[n]=low[p->nr];
}
int main()
{
ifstream fin("biconex.in");
fin>>n>>m;
int i,j;
Pnod p;
while(fin>>i>>j)
{
p=new(nod);
p->nr=j;
p->urm=l[i];
l[i]=p;
p=new(nod);
p->nr=i;
p->urm=l[j];
l[j]=p;
}
fin.close();
for(i=1;i<=n;i++)
dfn[i]=-1;
df(1,0,0);
fout<<contor<<'\n';
for(i=1;i<=contor;i++)
{
p=sol[i];
while(p)
{
fout<<p->nr<<" ";
p=p->urm;
}
fout<<'\n';
}
fout.close();
return 0;
}