Cod sursa(job #2798573)

Utilizator Pop_MariaPop Maria Pop_Maria Data 11 noiembrie 2021 16:16:03
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

class Graf
{
private:

    int numar_noduri, numar_muchii;
    vector <int> lista_adiacenta[100001];
    int numar = 0;

public:

    void citire();
    void dfs_biconex1();
    void dfs_biconex2(int, int, int &, stack <int> &, vector <vector <int>>&, vector <int> &, vector <int> &, vector<int> &);

};

/// functie de citire
void Graf :: citire()
{
    int capat_stang, capat_drept;

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);
        lista_adiacenta[capat_drept].push_back(capat_stang);
    }
}

void Graf :: dfs_biconex1()
{
    stack <int> st;
    vector <int> nivel1(numar_noduri + 1);
    vector <int> nivel2(numar_noduri + 1);
    vector <int> nivel3(numar_noduri + 1);
    vector <vector <int>> componente_biconexe(numar_noduri + 1);

    dfs_biconex2(1, 0, numar, st, componente_biconexe, nivel1, nivel2, nivel3);

    fout << numar << '\n';

    for(int i = 0; i < numar; i++)
    {
        for(int j = 0; j < componente_biconexe[i].size(); j++)
            fout << componente_biconexe[i][j] << " ";
        fout << '\n';
    }
}

void Graf :: dfs_biconex2(int x, int parinte, int &numar, stack <int> &st, vector <vector <int>>& componente_biconexe, vector <int> &nivel1, vector <int> &nivel2, vector <int> &nivel3)
{
        st.push(x);
        nivel2[x] = nivel2[parinte] + 1;
        nivel1[x] = nivel2[x];
        nivel3[x] = 1;

        for(int i = 0; i < lista_adiacenta[x].size(); i++)
        {
            int y = lista_adiacenta[x][i];

            if(parinte != y)
                if(nivel3[y] == 1)
            {
                if(nivel1[x] > nivel2[y])
                    nivel1[x] = nivel1[y];
            }
            else
            {
                dfs_biconex2(lista_adiacenta[x][i], x, numar, st, componente_biconexe, nivel1, nivel2, nivel3);
                if(nivel1[x] > nivel1[y])
                    nivel1[x] = nivel1[lista_adiacenta[x][i]];
                if(nivel2[x] <= nivel1[y])
                {
                    while(st.top() != y)
                    {
                        componente_biconexe[numar].push_back(st.top());
                        st.pop();
                    }

                    componente_biconexe[numar].push_back(y);
                    componente_biconexe[numar].push_back(x);
                    st.pop();
                    numar++;
                }
            }
        }
}

int main()
{
    Graf x;
    x.citire();
    x.dfs_biconex1();

    fin.close();
    fout.close();

    return 0;
}