Cod sursa(job #2784258)

Utilizator ionut31Ioan Ionescu ionut31 Data 16 octombrie 2021 10:47:43
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

ifstream fin("biconexe.in");
ofstream fout("biconexe.out");

struct muchie
{
    int x,y;
    muchie(int a, int b)
    {
        x=a;
        y=b;
    }
    muchie(){}
};

int vizitat[100005];
int moment[100005]; //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
int low[100005]; //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
stack<muchie> stiva; //stiva in care vom retine muchiile unei componente biconeexe
vector<set<int>> biconexe; //vectorul de componente biconexe


int n, m,timp=0; // start contor de timp pentru crearea vectorului moment

//liste de adiacente
vector<vector<int>> la;

//subprogram de determinare a componentelor biconexe
void bcx(int curent, int fiu)
{

    set<int> componenta;
    int a, b; //capetele unei muchii
    do
    {
        muchie m=stiva.top();
        stiva.pop();
        a=m.x;
        b=m.y;
        componenta.insert(a);
        componenta.insert(b);
    }while(a!=curent || b!=fiu);
    biconexe.push_back(componenta);//adaug componenta in vectorul de componente biconexe
}

//parcurgere dfs
void dfs(int x, int y) //x = nodul curent, y = parintele sau
{
    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            stiva.push(muchie(x,z));//adaug muchia in stiva de muchii
            dfs(z, x);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];


            //determinare componente biconexe
            if(moment[x] <= low[z]) //deci x este punct critic
                bcx(x, z);

        }
        else //am dat de o muchie de intoarcere
        {
            if(z!=y) //verific ca z sa nu fie parinte al lui x
            {    //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
                // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
                // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
                if (low[x] > moment[z])
                    low[x] = moment[z];
            }
        }
    }
}


int main()
{
    fin>>n>>m;
    la.resize(n+1);
    for(int i=0; i<m; ++i)
    {
        int x ,y;
        fin >> x >> y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

    dfs(1, 0);

    fout << biconexe.size() << "\n";

    for(int i=0; i<biconexe.size(); ++i)
    {
        for(set<int>::iterator it=biconexe[i].begin(); it!=biconexe[i].end(); ++it)
            fout << *it << " ";
        fout << "\n";
    }
}