Cod sursa(job #244998)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 16 ianuarie 2009 14:13:15
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#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;
}