Cod sursa(job #2470138)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 8 octombrie 2019 19:10:01
Problema Componente biconexe Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.93 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");


// In ant[i] retin daca pentru nodul i, pot sa ma intorc la un vecin "mai sus" decat tatal sau, mergand doar prin descendenti si doar o singura muchie de intoarcere.
// In ant[i] retin nivelul cel mai de sus in care pot sa ma intorc in acel fel

vector<int>v[100100];
stack<int>st;

int NR,t,tata[100100],viz[100100],ant[100100],nivel[100100],SL[100100],punct_articulatie[100100];

struct muchii_critice
{
    int p1,p2;
}sol[200010];

void DFS_puncte_articulatie(int nod)
{
    int vecin_urmator;

    ant[nod]=nivel[nod]; // initial ant[nod] este acelasi nivel ca nod (momentan nu am un vecin "mai sus" decat tatal sau direct
    viz[nod]=1;

    for(int i=0;i<v[nod].size();i++)
    {
        vecin_urmator=v[nod][i];
        if(viz[vecin_urmator]==0) // ma duc pe el
        {
            // Daca radacina(nodul 1) are mai mult de un vecini, atunci si el este punct de articulatie
            if(nod==1)NR++;

            viz[vecin_urmator]=1;
            nivel[vecin_urmator]=nivel[nod]+1;
            tata[vecin_urmator]=nod;

            DFS_puncte_articulatie(vecin_urmator);

            // Cand ma intorc din recursivitate, verific daca obtin un ant[] mai bun din descendenti
            if(ant[vecin_urmator] < ant[nod]) // inseamna ca pot sa plec din nod, iar prin descendenti sa ajung la vecin_urmator si sa ma intorc asemenea nodului vecin_urmator, MAI SUS, doar printr-o singura muchie de intoarcere
                ant[nod]=ant[vecin_urmator];

            // Acum cand m-am intors din recusivitate, daca ant[vecin_urmator] nu este mai mic decat nivelul tatalui sau, inseamna ca "vecin_urmator", care este un descendent pentru nod, este dependent de tatal sau (de nod), deci tatal sau este un punct de articulatie
            if(ant[vecin_urmator] >= nivel[nod])
                punct_articulatie[nod]=1;
        }
        else
        {
            // Daca nodul este deja marcat, inseamna ca este un nod cu un nivel mai mic in spate
            // Daca nu este chiar tatal direct, atunci dau update la ant[nod] cu acel vecin
            if(tata[nod]!=vecin_urmator && nivel[vecin_urmator]<ant[nod])ant[nod]=nivel[vecin_urmator];
        }
    }
}

// La muchii se rezolva ca si la puncte. Daca un punct nu are un drum de intaorcere "mai sus" decat tatal sau, atunci muchia (x,tata[x]) este muchie critica
void DFS_muchii_critice(int nod)
{
    int vecin_urmator;

    ant[nod]=nivel[nod]; // initial ant[nod] este acelasi nivel ca nod (momentan nu am un vecin "mai sus" decat tatal sau direct
    viz[nod]=1;

    for(int i=0;i<v[nod].size();i++)
    {
        vecin_urmator=v[nod][i];
        if(viz[vecin_urmator]==0) // ma duc pe el
        {
            viz[vecin_urmator]=1;
            nivel[vecin_urmator]=nivel[nod]+1;
            tata[vecin_urmator]=nod;

            DFS_muchii_critice(vecin_urmator);

            // Cand ma intorc din recursivitate, verific daca obtin un ant[] mai bun din descendenti
            if(ant[vecin_urmator] < ant[nod]) // inseamna ca pot sa plec din nod, iar prin descendenti sa ajung la vecin_urmator si sa ma intorc asemenea nodului vecin_urmator, MAI SUS, doar printr-o singura muchie de intoarcere
                ant[nod]=ant[vecin_urmator];

            // Acum cand m-am intors din recusivitate, daca ant[vecin_urmator] nu este mai mic decat nivelul tatalui sau, inseamna ca "vecin_urmator", care este un descendent pentru nod, este dependent de tatal sau (de nod), deci muchia tata-fiu este critica
            // In schimb daca ant[vecin_urmator] este chiar EGAL cu nivelul tatalui sau, inseamnca ca "vecin_urmator", care este un descendent pentru nod, poate ajunge prin intermediul propriilor descendenti si ai unei muchii de intaorcere la nod, formand astfel un "ciclu". In acest caz, muchia (x, tata[x]) nu mai reprezinta o muchie critica.
            if(ant[vecin_urmator] > nivel[nod])
                {
                    t++;
                    sol[t].p1=nod;
                    sol[t].p2=vecin_urmator;
                }
        }
        else
        {
            // Daca nodul este deja marcat, inseamna ca este un nod cu un nivel mai mic in spate
            // Daca nu este chiar tatal direct, atunci dau update la ant[nod] cu acel vecin
            if(tata[nod]!=vecin_urmator && nivel[vecin_urmator]<ant[nod])ant[nod]=nivel[vecin_urmator];
        }
    }
}


// La componente se rezolva la fel ca la puncte critice, doar ca tin salvate intr-o stiva nodurile pe care le parcurg pe parcurs
void DFS_biconex(int nod)
{
    int vecin_urmator;

    st.push(nod);

    ant[nod]=nivel[nod]; // initial ant[nod] este acelasi nivel ca nod (momentan nu am un vecin "mai sus" decat tatal sau direct
    viz[nod]=1;

    for(int i=0;i<v[nod].size();i++)
    {
        vecin_urmator=v[nod][i];
        if(viz[vecin_urmator]==0) // ma duc pe el
        {
            viz[vecin_urmator]=1;
            nivel[vecin_urmator]=nivel[nod]+1;
            tata[vecin_urmator]=nod;

            DFS_biconex(vecin_urmator);

            // Cand ma intorc din recursivitate, verific daca obtin un ant[] mai bun din descendenti
            if(ant[vecin_urmator] < ant[nod]) // inseamna ca pot sa plec din nod, iar prin descendenti sa ajung la vecin_urmator si sa ma intorc asemenea nodului vecin_urmator, MAI SUS, doar printr-o singura muchie de intoarcere
                ant[nod]=ant[vecin_urmator];

            // Cand am gasit un nod de articulatie, inseamnca ca toate nodurile parcurse de la el incolo formeaza o componenta biconeza si o afisez.
            if(ant[vecin_urmator] >= nivel[nod])
                {
                    t=0;
                    while(st.top()!=nod)
                    {
                        t++;
                        SL[t]=st.top();
                        st.pop();
                    }
                    t++; SL[t]=st.top(); // il pun si pe el, dar nu il sterg, pentru ca el face parte din mai multe componente

                    //g<<t<<" ";
                    for(i=t;i>=1;i--)g<<SL[i]<<" ";
                    g<<'\n';
                }
        }
        else
        {
            // Daca nodul este deja marcat, inseamna ca este un nod cu un nivel mai mic in spate
            // Daca nu este chiar tatal direct, atunci dau update la ant[nod] cu acel vecin
            if(tata[nod]!=vecin_urmator && nivel[vecin_urmator]<ant[nod])ant[nod]=nivel[vecin_urmator];
        }
    }
}

int cerinta,x,y,nr, n,m,i;
int main()
{
    //f>>cerinta;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    if(cerinta==2)
    {
        // Puncte de articulatie
        nivel[1]=1;
        DFS_puncte_articulatie(1);
        if(NR>=2)punct_articulatie[1]=1;
        else punct_articulatie[1]=0;

        nr=0;


        for(i=1;i<=n;i++)
        {
            if(punct_articulatie[i]==1)nr++;
        }
        g<<nr<<'\n';

        for(i=1;i<=n;i++)
        {
            if(punct_articulatie[i]==1)g<<i<<" ";
        }
    }
    else if(cerinta==3)
    {
        // Muchii Critice
        nivel[1]=1;
        DFS_muchii_critice(1);

        g<<t<<'\n';
        for(i=1;i<=t;i++)
            g<<sol[i].p1<<" "<<sol[i].p2<<'\n';
    }
    else
    {
        // Fac si puncte de articulatie sa stiu cate componente am
        nivel[1]=1;
        DFS_puncte_articulatie(1);
        if(NR>=2)punct_articulatie[1]=1;
        else punct_articulatie[1]=0;

        nr=0;

        for(i=1;i<=n;i++)
        {
            if(punct_articulatie[i]==1)nr++;
        }
        g<<nr+1<<'\n';

        // Reinitializez
        for(i=1;i<=n;i++)
        {
            nivel[i]=0;
            viz[i]=0;
            ant [i]=0;
        }

        // Componente Biconexe
        nivel[1]=1;
        DFS_biconex(1);
    }
    return 0;
}