Cod sursa(job #2012279)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 18 august 2017 14:10:18
Problema Componente biconexe Scor 84
Compilator cpp Status done
Runda Arhiva educationala Marime 3.51 kb
#include <fstream>
#define nmax 100001
#define mmax 200001
using namespace std;
fstream f1("biconex.in", ios::in);
fstream f2("biconex.out", ios::out);
long int n, m, aux[nmax], cap[nmax], v[2*mmax], level[nmax], low[nmax], nrcomp, vf, capb[nmax], comp[nmax], nrel, vect[nmax];
struct muchii
{
    long int x, y;
}muc[mmax], stiva[mmax];
void citire()
{
    long int i, x, y;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>muc[i].x>>muc[i].y;
        aux[muc[i].x]++;
        aux[muc[i].y]++;
    }
    cap[1]=1;
    for(i=2; i<=n+1; i++)
    {
        cap[i]=cap[i-1]+aux[i-1];
        aux[i-1]=cap[i-1];
    }
    for(i=1; i<=m; i++)
    {
       x=muc[i].x;
       y=muc[i].y;
       v[aux[x]]=y;
       aux[x]++;
       v[aux[y]]=x;
       aux[y]++;
    }
}
///nrel=nr el comp biconexa curenta
///nrcomp= nr comp biconexe
///capb[i]=indice sf a i-a comp biconexa in vect comp
void insereaza(long int st, long int dr, long int val)
{
    if(st<=dr)
    {
        long int mijl=(st+dr)/2;
        if(val==vect[mijl]);
        else if(val< vect[mijl]) insereaza(st, mijl-1, val);
             else insereaza(mijl+1, dr, val);
    }
    else
    {
        long int i;
        for(i=nrel; i>=st; i--)
            vect[i+1]=vect[i];
        vect[st]=val;
        nrel++;
    }
}
void comp_biconexa(long int x, long int y)
{
    long int sf, i;
    nrel=0;
    nrcomp++;

    while((stiva[vf].x!= x)||(stiva[vf].y!=y))
    {
        insereaza(1, nrel, stiva[vf].x);///in vect v
        insereaza(1, nrel, stiva[vf].y);
        vf--;
    }
    insereaza(1, nrel, stiva[vf].x);
    insereaza(1, nrel, stiva[vf].y);
    vf--;

    sf=capb[nrcomp-1];
    for(i=1; i<=nrel; i++)
    {
        sf++;
        comp[sf]=vect[i];
    }
    capb[nrcomp]=sf;
}
///level[i]= nivel nod i
///low[i]= cel mai mic nivel al unui nod in care poti ajunge din i pe un lant al descendentilor lui i si/sau o muchie de intoarcere
///low[i]=min(level[i], low[fiu_i], level[x] daca x-i muchie de intoacere)
void dfs(long int nod, long int tata, long int niv)
{
    long int i, nod2;
    low[nod]=level[nod]=niv;   ///init nivelul lui nod si low
    for(i=cap[nod]; i<cap[nod+1]; i++) ///pt fiecare vecin al lui nod= nod2
    {
        nod2=v[i];
        if(nod2!=tata)        ///daca nod2 nu e tata
        {
             if(level[nod2]==-1) ///daca nod2 fiu al lui nod
            {
                vf++; stiva[vf].x=nod; stiva[vf].y=nod2; ///pui muchia nod-nod2 in stiva
                dfs(nod2, nod, niv+1);                   ///apelezi dfs pt nod2
                low[nod]=min(low[nod], low[nod2]);       ///actualizezi low
                if(low[nod2]>=level[nod]) comp_biconexa(nod, nod2); ///daca nod= pct de art din nodurile
                ///tuturor muchiile bagate pana la nod-nod2 inclusiv formezi o noua comp biconexa

            }  ///daca nod-nod2 e muchie de intoarcere
              else low[nod]=min(low[nod], level[nod2]);  ///actualizezi low
        }
    }
}
void init()
{
    long int i;
    for(i=1; i<=n; i++)
        level[i]=-1;
}
void afisare()
{
    long int i, j;
    f2<<nrcomp<<"\n";
    for(i=1; i<=nrcomp; i++)
       {
        for(j=capb[i-1]+1; j<=capb[i]; j++)
            f2<<comp[j]<<" ";
        f2<<"\n";
       }

}
int main()
{
    citire();///citesti date+ creezi lista de adiacenta
    init(); ///init nivelurile cu -1
    dfs(1, 0, 0);///apelezi fct pt nodul rad, situat pe nivelul 0
    afisare();///afisezi comp biconexe
    return 0;
}