Pagini recente » Cod sursa (job #2701795) | Cod sursa (job #2602546) | Cod sursa (job #2395073) | Cod sursa (job #1161895) | Cod sursa (job #365993)
Cod sursa(job #365993)
#include<fstream>
#define Nmax 100001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,vf_stiva;
int dfn[Nmax],low[Nmax];
int numar_componente,nr_ordine;
int viz[Nmax];
struct nod
{int info;
nod *urm;
};
nod *l[Nmax],*a[Nmax];
struct muchie
{int tata,fiu;
};
muchie stiva[Nmax];
void citire()
{int i,x,y,m;
fin>>n>>m;
for(i=1;i<=m;i++)
{fin>>x>>y;
nod *c;
c=new nod;
c->info=y;
c->urm=l[x];
l[x]=c;
c=new nod;
c->info=x;
c->urm=l[y];
l[y]=c;
}
}
int minim(int x,int y)
{if(x>y) return y;
return x;
}
void salvare(int x,int u)
{muchie p;
nod *c;
int gasit=0;
do{p=stiva[vf_stiva];
vf_stiva--;
c=new nod;
c->info=p.tata;
c->urm=a[numar_componente];
a[numar_componente]=c;
}while(p.tata!=u || p.fiu!=x);
for(c=a[numar_componente];c!=NULL && gasit==0;c=c->urm)
if(c->info==p.fiu) gasit=1;
if(gasit==0)
{c=new nod;
c->info=p.fiu;
c->urm=a[numar_componente];
a[numar_componente]=c;
}
}
void biconex(int u,int tatal)
{int x;
nod *c;
nr_ordine++;
dfn[u]=low[u]=nr_ordine;
for(c=l[u];c!=NULL;c=c->urm)
{x=c->info;
if(x!=tatal && dfn[x]<dfn[u])
{vf_stiva++;
stiva[vf_stiva].tata=u;
stiva[vf_stiva].fiu=x;
}
if(dfn[x]==0)
{biconex(x,u);
low[u]=minim(low[u],low[x]);
if(low[x]>=dfn[u])
{numar_componente++;
salvare(x,u);
}
}
else
if(x!=tatal)
low[u]=min(low[u],dfn[x]);
}
}
int main()
{int i;
nod *c;
citire();
stiva[1].tata=-1;
stiva[1].fiu=3;
biconex(3,-1);
fout<<numar_componente<<'\n';
for(i=1;i<=numar_componente;i++)
{for(c=a[i];c!=NULL;c=c->urm)
fout<<c->info<<" ";
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}