Cod sursa(job #1712707)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 3 iunie 2016 14:53:02
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#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++;
}