Cod sursa(job #3269796)

Utilizator stefan0211Tacu Darius Stefan stefan0211 Data 20 ianuarie 2025 19:23:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

// struct ComponentaBiconexa
// {
//     set<int> noduri;
//     vector<pair<int, int>> muchii;
// };

ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
vector<set<int>> la;
set<int> noduri_critice;
vector<bool> viz;
vector<int> nivel_min, nivel;
// vector<ComponentaBiconexa> componente_biconexe;
vector<set<int>> componente_biconexe;
stack<pair<int, int>> stiva_componente_biconexe;

void Read()
{
    f >> n >> m;

    la.resize(n + 1);
    nivel_min.resize(n + 1, 0);
    nivel.resize(n + 1, 0);
    viz.resize(n + 1, false);

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        la[x].insert(y);
        la[y].insert(x);
    }
}

void df(int nod_curent)
{
    viz[nod_curent] = true;
    nivel_min[nod_curent] = nivel[nod_curent];
    int copii = 0;

    for (auto &vecin : la[nod_curent])
    {
        if (viz[vecin] == 0)
        {
            copii++;
            nivel[vecin] = nivel[nod_curent] + 1;
            stiva_componente_biconexe.push({nod_curent, vecin});
            df(vecin);

            nivel_min[nod_curent] = min(nivel_min[nod_curent], nivel_min[vecin]);

            // avem componentă biconexă
            if (nivel_min[vecin] >= nivel[nod_curent])
            {
                auto &componenta = componente_biconexe.emplace_back();
                while (stiva_componente_biconexe.top() != make_pair(nod_curent, vecin))
                {
                    auto &pereche = stiva_componente_biconexe.top();
                    stiva_componente_biconexe.pop();
                    componenta.insert(pereche.first);
                    componenta.insert(pereche.second);
                }

                auto &pereche = stiva_componente_biconexe.top();
                stiva_componente_biconexe.pop();
                componenta.insert(pereche.first);
                componenta.insert(pereche.second);
            }
        }
        else if (nivel[vecin] < nivel[nod_curent] - 1)
        {
            nivel_min[nod_curent] = min(nivel_min[nod_curent], nivel[vecin]);
            stiva_componente_biconexe.push({nod_curent, vecin});
        }
    }
}

int main()
{
    Read();

    nivel[1] = 1;
    df(1);

    g << componente_biconexe.size() << '\n';
    for (auto &componenta : componente_biconexe)
    {
        for (auto &nod : componenta)
        {
            g << nod << ' ';
        }
        g << '\n';
    }

    return 0;
}