Pagini recente » Cod sursa (job #2204017) | Cod sursa (job #2827024) | Cod sursa (job #2823319) | Cod sursa (job #3218916) | Cod sursa (job #1870580)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
int val;
nod *urm;
};
struct segment
{
int x,y;
};
segment stiva[400003];
int afis[400010],adafis,total;
typedef nod *pnod;
pnod p,v[100003];
int ind[100003],cur,minim[100003],t[100003],index,ss;
void ad(int x,int y)
{
p=new nod;
p->val=y;
p->urm=v[x]->urm;
v[x]->urm=p;
}
void dfs(int inc)
{
index+=1;
ind[inc]=index;
minim[inc]=index;
ss+=1;
stiva[ss].x=inc;
pnod p;
p=v[inc]->urm;
while(p)
{
if(ind[p->val]==0)
{
t[p->val]=inc;
stiva[ss].y=p->val;
dfs(p->val);
minim[inc]=min(minim[inc],minim[p->val]);
if(ind[inc]<=minim[p->val])
{
total+=1;
cur=adafis+1;
while(stiva[ss].x!=inc and stiva[ss].y!=p->val)
{
adafis+=1;
afis[adafis]=stiva[ss].x;
ss--;
}
adafis+=1;
afis[adafis]=inc;
/* adafis+=1;
afis[adafis]=p->val;*/
adafis+=1;
afis[adafis]=0;
sort(afis+cur,afis+adafis);
}
}
else
if(t[inc]!=p->val and minim[inc]>ind[p->val])
minim[inc]=ind[p->val];
p=p->urm;
}
}
int main()
{
int n,m,x,y,i,k;
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(ind[i]==0)
{
index=0;
ss=0;
dfs(i);
}
}
g<<total<<'\n';
k=1;
for(i=1;i<=total;i++)
{
while(afis[k]!=0)
{
g<<afis[k]<<" ";
k+=1;
}
k+=1;
g<<'\n';
}
return 0;
}