Pagini recente » Cod sursa (job #129775) | Cod sursa (job #2029108) | Cod sursa (job #503218) | Cod sursa (job #2826124) | Cod sursa (job #1712707)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100100
#define M 400100
#define vec lis[i].val
using namespace std;
int head[N],prenum[N],tata[N];
int viz[N],low[N];
int ifin;
int nrbic,nrmuc;
int stk[N],sp;
int sol[M],x,nrsol;
void Add_sol(int x){
sol[nrsol++]=x;
}
void push(int x){
stk[sp++]=x;
}
int pop(){
return stk[--sp];
}
struct muc{
int val,next;
};
struct muc lis[M];
int cnt;
void dfs(int k){
int i;
push(k);
viz[k]=1;
cnt++; prenum[k]=cnt; low[k]=cnt;
for(i=head[k]; i!=-1 ;i=lis[i].next){
if(viz[vec]==0){
tata[vec]=k;
dfs(vec);
low[k]=min(low[k],low[vec]);
if(prenum[k]<=low[vec] ){
nrbic++;
do{
x=pop();
Add_sol(x);
}while(x!=k);
push(k);
Add_sol(-1);
}
}else{
if(tata[k]!=vec && prenum[vec]<prenum[k]){
low[k]=min(low[k],prenum[vec]);
}
}
}
}
void Add_Muc(int x,int y);
int main(){
int n,m,i,x,y;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
memset(head,-1, (n+1)*sizeof(int) );
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
Add_Muc(x,y);
Add_Muc(y,x);
}
dfs(1);
printf("%d\n",nrbic);
for(i=0;i<nrsol;i++){
if(sol[i]==-1){
printf("\n");
continue;
}
printf("%d ",sol[i]);
}
return 0;
}
void Add_Muc(int x,int y){
lis[ifin].val=y;
lis[ifin].next=head[x];
head[x]=ifin;
ifin++;
}