Cod sursa(job #1642709)

Utilizator Julian.FMI Caluian Iulian Julian. Data 9 martie 2016 15:48:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define nmax 100099
using namespace std;
long *g[nmax];
long sx[nmax],st[nmax],dfn[nmax],low[nmax];
long to,num,n,vf;
long *re[nmax];
char viz[nmax];

ifstream fin("biconex.in");
ofstream fout("biconex.out");
void citire()
{long i,m,x,y;
    fin>>n>>m;
    for(i=1;i<=n;i++){g[i]=(long*)realloc(g[i],sizeof(long));g[i][0]=0;}
    for(i=1;i<=m;i++)
    {fin>>x>>y;
    g[x][0]++;g[x]=(long*)realloc(g[x],(g[x][0]+1)*sizeof(long));
    g[x][g[x][0]]=y;
    g[y][0]++;g[y]=(long*)realloc(g[y],(g[y][0]+1)*sizeof(long));
    g[y][g[y][0]]=x;
    }
}

void afisare(long u,long tu)
{long i,x,y,cont=0;
cont=0;
to++;
re[to]=(long*)realloc(re[to],sizeof(long));

re[to][0]=0;
    do{x=sx[vf]; y=st[vf]; vf--;
    if(!viz[x]){
    re[to][0]++;
    re[to]=(long*)realloc(re[to],sizeof(long)*(re[to][0]+1));
    re[to][re[to][0]]=x;
    viz[x]=1;}

       if(!viz[y]){
    re[to][0]++;
    re[to]=(long*)realloc(re[to],sizeof(long)*(re[to][0]+1));
    re[to][re[to][0]]=y;
    viz[y]=1;}

    }while(x!=u || y!=tu);

    for(i=1;i<=re[to][0];i++)viz[re[to][i]]=0;
}

void initializare()
{for(long i=1;i<=n;i++)dfn[i]=-1;
vf=0;
sx[vf]=1;st[vf]=-1;
}

void biconex(long u,long tu)
{long i,x;
//cout<<u<<' '<<tu<<endl;
dfn[u]=low[u]=++num;
    for(i=1;i<=g[u][0];i++)
    {x=g[u][i];
  //  cout<<u<<"->"<<x<<endl;
    if(x!=tu && dfn[x]<dfn[u])
    {sx[++vf]=x; st[vf]=u;
   // cout<<"da";
    }

    if(dfn[x]==-1)
    {
        biconex(x,u);
        low[u]=min(low[x],low[u]);
        if(low[x]>=dfn[u])
            afisare(x,u);

    }else if(x!=tu)low[u]=min(low[u],dfn[x]);

    }
}

int main()
{long i,j;
    citire();
    initializare();
    biconex(1,-1);
    fout<<to<<'\n';
    for(i=1;i<=to;i++)
        {for(j=1;j<=re[i][0];j++)fout<<re[i][j]<<' ';
        fout<<'\n';}
}