Pagini recente » Cod sursa (job #2636278) | Cod sursa (job #1352385) | Cod sursa (job #2864166) | Cod sursa (job #2649610) | Cod sursa (job #244998)
Cod sursa(job #244998)
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <algorithm>
#include <vector>
#define nMax 100005
#define pb push_back
using namespace std;
struct per{int x;int y;};
long n,m,i,j,n1,n2,g[nMax],nr[nMax],low[nMax],COMP;
per aux,a[200005];
int *v[nMax];
vector <int>B[nMax];
stack <per> Q;
void sol(const int x, const int y);
void DF(const int nod, const int tata, int index){
nr[nod]=low[nod]=index;
for (int i=0;i<g[nod];++i){
int fiu=v[nod][i];
if (tata==fiu)continue;
if (nr[fiu]==-1){
/////////
aux.x=nod;aux.y=fiu;Q.push(aux);
////////
DF(fiu,nod,index+1);
if (low[fiu]<low[nod])low[nod]=low[fiu];
if (low[fiu]>=nr[nod])sol(nod,fiu);
}else if (nr[fiu] < low[nod]) low[nod]=nr[fiu];
}
}
void sol(const int x, const int y){
int a,b;
do{
a=(Q.top()).x; b=(Q.top()).y; Q.pop();
B[COMP].pb(a);B[COMP].pb(b);
}while (a!=x||b!=y);
COMP++;
}
int main(){
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%ld %ld",&n,&m);
for (i=1;i<=m;++i){
scanf("%ld %ld",&a[i].x,&a[i].y);
g[a[i].x]++;g[a[i].y]++;
}
for (i=1;i<=n;++i)v[i]=(int*)malloc(g[i]*sizeof(int)),g[i]=0;
for (i=1;i<=m;++i){
n1=a[i].x;n2=a[i].y;
v[n1][g[n1]++]=n2;
v[n2][g[n2]++]=n1;
}
for (i=1;i<=n;++i)nr[i]=-1;
DF(1,0,0);
printf("%ld\n",COMP);
for (i=0;i<COMP;++i){
sort(B[i].begin(), B[i].end());
for (j=0;j<B[i].size();++j)
if (j==0)printf("%ld ",B[i][j]);
else if (B[i][j]!=B[i][j-1])printf("%ld ",B[i][j]);
printf("\n");
}
return 0;
}