Pagini recente » Cod sursa (job #1605640) | Cod sursa (job #757163) | Cod sursa (job #1180901) | Cod sursa (job #1351179) | Cod sursa (job #392524)
Cod sursa(job #392524)
#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,vfst;
int d[Nmax],l[Nmax],nr;
void baga(int a, int b)
{
int x,y;
nrb++;
do
{
x=st[vfst].f;
y=st[vfst].t;
vfst--;
sol[nrb].push_back(y);
}
while(x!=a || y!=b);
sol[nrb].push_back(x);
}
void biconex(int nod, int tnod)
{
nr++;
d[nod]=l[nod]=nr;
for (int i=0;i<G[nod].size();++i)
{
int x=G[nod][i];
if (x!=tnod && d[x]<d[nod])
{
vfst++;
st[vfst].f=x;
st[vfst].t=nod;
}
if (d[x]==-1)
{
biconex(x,nod);
l[nod]=min(l[x],l[nod]);
if (l[x]>=d[nod])
baga(x,nod);
}
else
if (x!=tnod)
l[nod]=min(l[nod],d[x]);
}
}
int main()
{
int i,x,y,j;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d", &n, &m);
for (i=1;i<=m;++i)
{
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
//initializari
for (i=1;i<=n;++i)
d[i]=l[i]=-1;
st[0].f=1;
st[0].t=-1;
vfst=0;
biconex(1,-1);
printf("%d\n", nrb);
for (i=1;i<=nrb;++i)
{
for (j=0;j<sol[i].size();++j)
printf("%d ", sol[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}