Cod sursa(job #2252579)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 2 octombrie 2018 20:31:23
Problema Componente biconexe Scor 54
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#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;
}