Cod sursa(job #3373584)

Utilizator carinaa_leetAmarie Carina carinaa_leet Data 7 noiembrie 2026 12:09:57
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int m, n;
vector<vector<int>> adj;
vector<int> niv;
vector<int> niv_min;
vector<int> viz;
stack<pair<int, int>> st;
vector<set<int>> comp;

void DFS(int nod, int tata)
{
    viz[nod] = 1;

    if (tata == -1)
    {
        niv[nod] = 1;
    }
    else
    {
        niv[nod] = niv[tata] + 1;
    }

    niv_min[nod] = niv[nod]; // cel mai mic nivel al nodului este nivelul lui insusi

    for (int i : adj[nod])
    {
        if (i == tata)
            continue; // sarim peste muchia spre tata

        if (!viz[i])
        {
            st.push({nod, i});

            DFS(i, nod);

            niv_min[nod] = min(niv_min[nod], niv_min[i]);
            // actualizam daca copiii au gasit o muchie de intoarcere

            if (niv_min[i] >= niv[nod]) // am gasit comp biconexa
            {
                set<int> componenta_curenta;
                pair<int, int> muchie;

                // extragem muchiile de pe stiva pana la (nod,i) inclusiv
                do
                {
                    muchie = st.top();
                    st.pop();
                    // adaugam ambele capele ale muchiei in set
                    componenta_curenta.insert(muchie.first);
                    componenta_curenta.insert(muchie.second);
                } while (muchie != make_pair(nod, i) && muchie != make_pair(i, nod));

                comp.push_back(componenta_curenta);
            }
        }
        else if (niv[i] < niv[nod]) // sigur e muchie de intoarcere
        {
            st.push({nod, i});
            niv_min[nod] = min(niv_min[nod], niv[i]);
        }
    }
}

int main()
{
    fin >> n >> m;

    adj.resize(n + 1);
    niv.resize(n + 1, 0);         // niv este initial 0; niv in [1;m+1]
    niv_min.resize(n + 1, m + 1); // niv_min nu poate fi mai mare de m+1
    viz.resize(n + 1, 0);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!viz[i])
        {
            DFS(i, -1);
        }
    }

    fout << comp.size() << "\n";
    for (auto &elem : comp)
    {
        for (int nod_curent : elem)
        {
            fout << nod_curent << " ";
        }
        fout << "\n";
    }
    return 0;
}