Cod sursa(job #3307004)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 16 august 2025 12:56:24
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 100001;

vector<int> G[NMAX];
vector<vector<int>> compBiconexe;
int nivel[NMAX], nivelMinim[NMAX];

void addCompBiconexa(int x, int parent, stack<int> &S)
{
    /// parent este nodul critic
    vector<int> componenta{parent};
    int vf;
    do
    {
        vf = S.top();
        componenta.push_back(vf);
        S.pop();
    } while (vf != x);
    compBiconexe.push_back(componenta);
}

void DFS(int x, int parent, stack<int> &S)
{
    S.push(x);
    nivel[x] = nivel[parent] + 1; /// l-am vizitat
    nivelMinim[x] = nivel[x];
    for (auto vec: G[x])
    {
        if (vec == parent)
            continue;///nu vreau sa ma intorc in parinte
        if (nivel[vec] == 0) /// am descoperit un nod nou
        {
            DFS(vec, x, S);
            /// am terminat parcurgerea in sub-tree
            if (nivelMinim[vec] >= nivel[x]) /// copilul nu poate ajunge mai sus  de parinte
            {
                /// inseamna ca x este nod critic
                addCompBiconexa(vec, x, S);
            }
            nivelMinim[x] = min(nivelMinim[x],
                                nivelMinim[vec]); /// daca copilul reuseste sa urce mai sus de x, atunci si x o puate lua pe ac drum
            /// altfel nu este nod critic deci nu il procesez acum
        }
        else
        {
            /// avem muchie de intoarcere
            nivelMinim[x] = min(nivelMinim[x], nivel[vec]);
        }
    }
}

int main()
{
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        f >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    stack<int> S;
    DFS(1, 0, S);
    g << compBiconexe.size() << '\n';
    for (auto comp: compBiconexe)
    {
        for (auto node: comp)
        {
            g << node << ' ';
        }
        g << '\n';
    }
    return 0;
}