Pagini recente » Cod sursa (job #2242600) | Cod sursa (job #86837) | Cod sursa (job #2492871) | Cod sursa (job #2252579)
#include <cstdio>
#include <cstdlib>
#define NMax 100005
#define MMax 200005
#define min(a, b) (a<b?a:b)
#define max(a, b) (a>b?a:b)
using namespace std;
int N, M, *A[NMax], i, V1[NMax], V2[NMax], Vf, VfS, C, Deepest[NMax];
bool P;
struct S{
int first;
int second;
}List[MMax];
void Read();
void Solve(int Son, int Parent);
void Show(int i);
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
Read();
Solve(1, -1);
printf("%d\n", C);
for(i=1; i<=N; ++i)V1[i]=V2[i]=-1;
Vf=0; P=1;
for(i=1; i<=N; ++i)Deepest[i]=0;
Solve(1, -1);
return 0;
}
void Read(){
scanf("%d%d", &N, &M);
int x, y;
for(i=1; i<=N; ++i){
A[i]=(int *)realloc(A[i], sizeof(int));
A[i][0]=0;
V1[i]=V2[i]=-1;
}
for(i=1; i<=M; ++i){
scanf("%d%d", &x, &y);
++A[x][0];
A[x]=(int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
A[x][A[x][0]]=y;
++A[y][0];
A[y]=(int *)realloc(A[y], (A[y][0]+1)*sizeof(int));
A[y][A[y][0]]=x;
}
return;
}
void Solve(int Son, int Parent){
int i;
V1[Son]=V2[Son]=++Vf;
for(i=1; i<=A[Son][0]; ++i){
int X=A[Son][i];
if(X!=Parent && V1[Son]>V1[X] && V1[Son]>Deepest[X]){
List[++VfS].first=Son;
List[VfS].second=X;
Deepest[X]=max(Deepest[X], V1[Son]);
}
if(V1[X]==-1){
Solve(X, Son);
V2[Son]=min(V2[Son], V2[X]);
if(V2[X]>=V1[Son]){
if(!P)C++;
else Show(Son);
}
}
if(X!=Parent)V2[Son]=min(V2[Son], V1[X]);
}
return;
}
void Show(int i){
int k=0;
while(List[VfS].first!=i){
++k;
printf("%d ", List[VfS--].first);
}
printf("%d ", List[VfS].first);
if(!k)printf("%d ", List[VfS].second);
--VfS;
printf("\n");
return;
}