Pagini recente » Cod sursa (job #418465) | Cod sursa (job #663520) | Cod sursa (job #2199955) | Cod sursa (job #732915) | Cod sursa (job #581966)
Cod sursa(job #581966)
#include<stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,i,x,y,nrc,st[200001][2],idx[100001],low[100001];
struct nod{int y; nod *next;};
nod *G[100001];
vector<int> C[100001];
int add(int a,int b)
{
nod *nou=new nod;
nou->y=b;
nou->next=G[a];
G[a]=nou;
return 0;
}
int baga(int x, int y)
{
nrc++;
int tx,ty;
do
{
tx=st[st[0][0]][0];
ty=st[st[0][0]][1];
st[0][0]--;
C[nrc].push_back(tx);
C[nrc].push_back(ty);
}while(tx!=x || ty!=y);
return 0;
}
int df(int vf,int pred,int index)
{
idx[vf]=low[vf]=index;
nod *it=new nod;
it=G[vf];
while (it)
{
if (it->y==pred) {it=it->next;continue;}
if (idx[it->y]==-1)
{
st[++st[0][0]][0]=vf;
st[st[0][0]][1]=it->y;
df(it->y,vf,index+1);
if (low[vf]>low[it->y]) low[vf]=low[it->y];
if (low[it->y]>=idx[vf])
baga(vf,it->y);
}
else if (low[vf]>idx[it->y]) low[vf]=idx[it->y];
it=it->next;
}
}
int main(void)
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for (i=1;i<=n;i++)
{
idx[i]=-1;
low[i]=0;
}
df(1,0,0);
printf("%d\n",nrc);
vector<int>::iterator it;
for (i=1;i<=nrc;i++)
{
sort(C[i].begin(),C[i].end());
C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
for (it=C[i].begin();it!=C[i].end();it++)
{
printf("%d ",*it);
}
printf("\n");
}
return 0;
}