Pagini recente » Cod sursa (job #1886344) | Cod sursa (job #2378682) | Cod sursa (job #2404509) | Cod sursa (job #2542520) | Cod sursa (job #530295)
Cod sursa(job #530295)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
const int M=200005;
vector<int> L[N],SOL[N];
bool f[N];
int q,nrs,n,m,niv[N],low[N],tata[N],st[M][2];
void read()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
L[x].push_back(y);
L[y].push_back(x);
}
}
void df(int nod)
{
f[nod]=1;
low[nod]=niv[nod];
for(vector<int>::iterator it=L[nod].begin();it!=L[nod].end();it++)
{
int fiu=*it;
if(!f[fiu])
{
tata[fiu]=nod;
niv[fiu]=niv[nod]+1;
++q;
st[q][0]=nod;
st[q][1]=fiu;
df(fiu);
if(low[fiu]<low[nod])
low[nod]=low[fiu];
if(low[fiu]>=niv[nod])
{
++nrs;
while(!(st[q][0]==nod && st[q][1]==fiu))
{
SOL[nrs].push_back(st[q][0]);
SOL[nrs].push_back(st[q][1]);
--q;
}
SOL[nrs].push_back(st[q][0]);
SOL[nrs].push_back(st[q][1]);
--q;
}
}
else
{
if(tata[nod]!=fiu && niv[fiu]<niv[nod])
{
if(low[nod]>niv[fiu]) low[nod]=niv[fiu];
++q;
st[q][0]=nod;
st[q][1]=fiu;
}
}
}
}
void afis()
{
printf("%d\n",nrs);
for(int i=1;i<=nrs;i++)
{
int last=-1;
sort(SOL[i].begin(),SOL[i].end());
for(vector<int>::iterator it=SOL[i].begin();it!=SOL[i].end();it++)
{
if(*it!=last)
printf("%d ",*it);
last=*it;
}
printf("\n");
}
}
int main()
{
read();
df(1);
afis();
return 0;
}