Pagini recente » Cod sursa (job #2913055) | Cod sursa (job #1832758) | Cod sursa (job #1378699) | Cod sursa (job #1310005) | Cod sursa (job #1715355)
#include <fstream>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
int t[2][400001],start[100001],v[100001],n,m,l[100001],niv[100001],k,q,tata[100001],used[100001],nr1,radacina,st[2][100001],vf,sol[200001],p;
void citire ()
{
cin>>n>>m; int x,y;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
t[0][++k]=y; t[1][k]=start[x]; start[x]=k;
t[0][++k]=x; t[1][k]=start[y]; start[y]=k;
}
}
void add (int x,int y)
{
st[1][++vf]=y;
st[0][vf]=x;
}
void scoate (int x,int y)
{
while(3>2 && vf>0)
{
if((st[0][vf]==x && st[1][vf]==y) || (st[0][vf]==y && st[1][vf]==x)) break;
sol[++p]=st[1][vf]; vf--;
} sol[++p]=st[1][vf]; sol[++p]=st[0][vf]; vf--;
q++; sol[++p]=-1;
}
void dfs (int nod)
{
used[nod]=1;
l[nod]=niv[nod];
int p=start[nod];
while(p)
{
if(t[0][p]!=tata[nod] && niv[nod]>niv[t[0][p]])
add(nod,t[0][p]);
if(used[t[0][p]]==0)
{
niv[t[0][p]]=niv[nod]+1;
tata[t[0][p]]=nod;
if(radacina==nod) nr1++;
dfs(t[0][p]);
if(l[t[0][p]]<l[nod]) l[nod]=l[t[0][p]];
if(l[t[0][p]]>=niv[nod])
scoate(t[0][p],nod);
}
else if( tata[nod]!=t[0][p] && niv[t[0][p]]<l[nod]) l[nod]=niv[t[0][p]];
p=t[1][p];
}
}
void parcurg ()
{
niv[1]=1;
dfs(1);
}
void scrie ()
{ int k=1,care=1,y=0;
cout<<q<<"\n";
while(y<q)
{
if(sol[k]==-1) {care++; cout<<"\n";y++;}
else
if(v[sol[k]]<care)
{
v[sol[k]]=care; cout<<sol[k]<<" ";
} ++k;
}
}
int main()
{
citire();
parcurg();
scrie();
return 0;
}