Pagini recente » Cod sursa (job #2298539) | Cod sursa (job #1676912) | Cod sursa (job #2741252) | Cod sursa (job #1275424) | Cod sursa (job #1858319)
#include <fstream>
using namespace std;
struct eu{int x,y;};
eu st[200001];
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
int val;
nod *urm;
};
typedef nod *pnod;
pnod p,v[100003],v2[100003];
void ad(int x,int y)
{
p=new nod;
p->val=y;
p->urm=v[x]->urm;
v[x]->urm=p;
}
pnod t,r;
void adaug(int x,int y)
{
t=v2[y];
p=t->urm;
while(p and p->val<x)
{
t=p;
p=p->urm;
}
if(p)
{
r=new nod;
r->val=x;
r->urm=p;
t->urm=r;
}
else
{
r=new nod;
r->val=x;
r->urm=0;
t->urm=r;
}
}
int cate,i,n,j,m,nr,cate2,viz[100001],niv[100001],l[100001],marc[100001],tata[1000001],vc[100001],x,y,rad,cc;
void pas(int x,int y)
{
int q1=st[cate].x,q2=st[cate].y;
cate--;
cate2++;
v2[cate2]=new nod;
v2[cate2]->urm=0;
while(x!=q1&&y!=q2)
{
adaug(q2,cate2);
// adaug(q1,cate2);
q1=st[cate].x;
q2=st[cate].y;
cate--;
}
adaug(q1,cate2);
adaug(q2,cate2);
}
void dfs(int nod)
{
pnod p;
viz[nod]=1;
l[nod]=niv[nod];
p=v[nod]->urm;
while(p)
{
int f=p->val;
if(viz[f]==1)
{
if(f!=tata[nod] and l[nod]>niv[f])
l[nod]=niv[f];
}
else
{
st[++cate].x=nod;
st[cate].y=f;
if(nod==rad)
nr++;
niv[f]=niv[nod]+1;
tata[f]=nod;
dfs(f);
if(l[nod]>l[f])
l[nod]=l[f];
if(l[f]>=niv[nod])
{
marc[nod]=1;
pas(nod,f);
}
}
p=p->urm;
}
}
int main ()
{
f>>n>>m;
for(i=1;i<=n;i++)
{
v[i]=new nod;
v[i]->urm=0;
}
for(i=1;i<=m;i++)
{
f>>x>>y;
ad(x,y);
ad(y,x);
}
for(i=1;i<=n;i++)
if(viz[i]==0)
{
rad=i;
niv[i]=1;
cc++;
vc[cc]=i;
nr=0;
dfs(i);
if(nr>=2)
marc[i]=1;
else
marc[i]=0;
}
g<<cate2<<'\n';
for(i=1;i<=cate2;i++)
{
p=v2[i]->urm;
while(p)
{
g<<p->val<<" ";
p=p->urm;
}
g<<'\n';
}
return 0;
}