Pagini recente » Cod sursa (job #3005494) | Cod sursa (job #925902) | Cod sursa (job #2190662) | Cod sursa (job #134266) | Cod sursa (job #404423)
Cod sursa(job #404423)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define file_in "biconex.in"
#define file_out "biconex.out"
#define Nmax 213213
vector<int> G[Nmax],sol[Nmax];
int n,m;
struct bc
{
int f,t;
}
st[Nmax];
int nrb,vfs;
int d[Nmax],l[Nmax],nr,frecv[Nmax];
void baga(int a, int b)
{
int x,y;
nrb++;
do
{
x=st[vfs].f;
y=st[vfs].t;
vfs--;
sol[nrb].push_back(y);
}
while(x!=a || b!=y);
sol[nrb].push_back(x);
}
void biconex(int nod, int tnod)
{
int i,x;
nr++;
d[nod]=l[nod]=nr;
for (i=0;i<G[nod].size();++i)
{
x=G[nod][i];
if (x!=tnod && d[x]<d[nod])
{
st[++vfs].f=x;
st[vfs].t=nod;
}
if (d[x]==-1)
{
biconex(x,nod);
l[nod]=min(l[nod],l[x]);
if (l[x]>=d[nod]) baga(x,nod);
}
else
if (x!=tnod)
l[nod]=min(l[nod],d[x]);
}
}
int main()
{
int i,j,a,b,x;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d", &n, &m);
for (i=1;i<=m;++i)
{
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for (i=1;i<=n;++i)
d[i]=l[i]=-1;
st[0].f=1;
st[0].t=-1;
vfs=0;
biconex(1,-1);
printf("%d\n", nrb);
for (i=1;i<=nrb;++i)
{
int mm=0;
for (j=0;j<sol[i].size();++j)
{
x=sol[i][j];
frecv[x]++;
if (x>mm) mm=x;
}
//printf("%d ", sol[i][j]);
for (j=1;j<=mm;++j)
if (frecv[j]!=0){
printf("%d ",j);
frecv[j]=0;
}
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}