Pagini recente » Cod sursa (job #1909290) | Cod sursa (job #121966) | Cod sursa (job #1170389) | Cod sursa (job #2128086) | Cod sursa (job #392535)
Cod sursa(job #392535)
#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,frecv[Nmax];
char s[1000];
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);
//printf("%d %d\n", x,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", &n, &m);
for (i=1;i<=m;++i)
{
//scanf("%d %d", &x, &y);
x=y=0;
gets(s);
j=0;
while(s[j]>='0' && s[j]<='9')
{
x=x*10+s[j]-'0';
j++;
}
j++;
while(s[j]>='0' && s[j]<='9')
{
y=y*10+s[j]-'0';
j++;
}
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)
{
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;
}