Pagini recente » Cod sursa (job #2119880) | Cod sursa (job #1708852) | Cod sursa (job #645628) | Cod sursa (job #135249) | Cod sursa (job #1862756)
//Problema1
#include <fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
int val;
nod *urm;
};
typedef nod *pnod;
pnod v[100003],p,v2[100003],ultim;
int viz[100003];
int cate,i,n,j,m,nr,cate2,pc,niv[100003],l[100003],marc[100003],tata[100003],vc[100003],x,y,rad,cc;
void ad(int x,int y)
{
p=new nod;
p->val=y;
p->urm=v[x]->urm;
v[x]->urm=p;
}
int index,ss;
struct acum
{
int x,y;
};
acum st[200002];
pnod rt;
int op;
pnod t,rty;
void adaug(int a,int e)
{
t=v2[e];
p=v2[e]->urm;
while(p and p->val<a)
{
t=p;
p=p->urm;
}
if(p)
{
rty=new nod;
rty->val=a;
rty->urm=p;
t->urm=rty;
}
else
{
rty=new nod;
rty->val=a;
rty->urm=0;
t->urm=rty;
}
}
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;
ultim=v2[cate2];
while(x!=q1 and y!=q2)
{
/* rt=new nod;
rt->val=q1;
rt->urm=v2[cate2]->urm;
v2[cate2]->urm=rt;*/
adaug(q2,cate2);
q1=st[cate].x;
q2=st[cate].y;
cate--;
}
adaug(q2,cate2);
adaug(q1,cate2);
//v2[cate2]->urm=rt;
}
void dfs(int nod)
{
int i;
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;
}