Pagini recente » Cod sursa (job #2204318) | Cod sursa (job #2619587) | Cod sursa (job #870593) | Cod sursa (job #2223022) | Cod sursa (job #530303)
Cod sursa(job #530303)
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 100005
#define LMAX 200005
#define pb push_back
using namespace std;
int n,m,r,dad[NMAX],up[NMAX],lvl[NMAX],rez;
vector <int> A[NMAX],S[NMAX];
struct muchie{int a,b;};
muchie B[LMAX];
char viz[NMAX];
void read()
{
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
A[x].pb(y);
A[y].pb(x);
}
}
void dfs(int nod)
{
viz[nod]=1;
int i,fiu;
up[nod]=lvl[nod];
for (i=0; i<A[nod].size(); i++)
{
fiu=A[nod][i];
if (!viz[fiu])
{
lvl[fiu]=lvl[nod]+1;
dad[fiu]=nod;
B[++r].a=nod; B[r].b=fiu;
dfs(fiu);
if (up[nod]>up[fiu]) up[nod]=up[fiu];
if (up[fiu]>=lvl[nod])
{
rez++;
while (B[r].a!=nod || B[r].b!=fiu)
{
S[rez].pb(B[r].a);
S[rez].pb(B[r].b);
r--;
}
S[rez].pb(B[r].a);
S[rez].pb(B[r].b);
r--;
}
}
else
if (dad[nod]!=fiu && lvl[fiu]<lvl[nod])
{
if (up[nod]>lvl[fiu]) up[nod]=lvl[fiu];
B[++r].a=nod; B[r].b=fiu;
}
}
}
void show()
{
printf("%d\n",rez);
int i,j,val;
for (i=1; i<=rez; i++)
{
sort(S[i].begin(),S[i].end());
val=0;
for (j=0; j<S[i].size(); j++)
if (S[i][j]!=val)
{
printf("%d ",S[i][j]);
val=S[i][j];
}
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
read();
dfs(1);
show();
return 0;
}