Pagini recente » Cod sursa (job #705258) | Cod sursa (job #2575355) | Cod sursa (job #2533448) | Cod sursa (job #2984427) | Cod sursa (job #630555)
Cod sursa(job #630555)
# include <fstream>
#define minim(x,y) (x<y? x:y)
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
int n,m,x,y,nr,nrdf[100005],v[100005],k,tata[100005],i;
struct nod
{
int info;
nod *urm;
}*a[100005],*p,*cb[100005];
class stiva
{
public:
int vf;
int sti[200005],stj[200005];
stiva (){vf=0;}
void push (int x,int y)
{
vf++;
sti[vf]=x;
stj[vf]=y;
}
void pop (int &i,int &j)
{
i=sti[vf];
j=stj[vf];
vf--;
}
}st;
void biconex (int i)
{
nr++;
nrdf[i]=nr;
v[i]=nr;
nod *p;
p=a[i];
while (p)
{
if (nrdf[p->info]==0)
{
st.push (i,p->info);
tata[p->info]=i;
biconex (p->info);
v[i]=minim (v[i],v[p->info]);
if (v[p->info]>=nrdf[i])
{
int x,y;
k++;
while (!(st.sti[st.vf]==i && st.stj[st.vf]==p->info) && st.vf>0)
{
nod *p;
st.pop (x,y);
p=new nod;
p->info=y;
p->urm=cb[k];
cb[k]=p;
}
if (st.vf!=0)
{
nod *p;
st.pop (x,y);
p=new nod;
p->info=x;
p->urm=cb[k];
cb[k]=p;
p=new nod;
p->info=y;
p->urm=cb[k];
cb[k]=p;
}
}
}
else
if (tata[i]!=p->info)
v[i]=minim (v[i],nrdf[p->info]);
p=p->urm;
}
}
int main ()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
p=new nod;
p->info=y;
p->urm=a[x];
a[x]=p;
p=new nod;
p->info=x;
p->urm=a[y];
a[y]=p;
}
for (i=1;i<=n;i++)
if (nrdf[i]==0)
biconex (i);
g<<k<<"\n";
for (i=1;i<=k;i++)
{
p=cb[i];
while (p)
{
g<<p->info<<" ";
p=p->urm;
}
g<<"\n";
}
return 0;
}