Cod sursa(job #3374917)

Utilizator tenirinaIrina Tenita tenirina Data 9 noiembrie 2026 19:06:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, m;
vector<int> graf[100001];
vector<int> componente[100001];   // componente[c] nodurile componentei biconexe c
vector<int> stiva;                // nodurile parcurse si inca nepuse intr-o comp
int nivel[100001];                // nivel[x] adancimea lui x in arborele dfs (0 - nevizitat)
int low[100001];                  // low[x] cel mai de sus nivel la care se pot ajunge din subarbrl lui x
int nr_componente;

void dfs(int nod, int parinte)
{
    stiva.push_back(nod);
    low[nod] = nivel[nod];
    for (int vecin : graf[nod])
    {
        if (vecin == parinte)
        {
            continue;
        }
        if (nivel[vecin] != 0)
        {
            // muchie de intoarcere, la ce nivel ajunge
            low[nod] = min(low[nod], nivel[vecin]);
        }
        else
        {
            nivel[vecin] = nivel[nod] + 1;
            dfs(vecin, nod);
            low[nod] = min(low[nod], low[vecin]);

            // daca vecin nu poate sa urce mai sus de nod, nod rupe/desparte o componenta
            if (low[vecin] >= nivel[nod])
            {
                nr_componente++;
                while (stiva.back() != vecin)
                {
                    componente[nr_componente].push_back(stiva.back());
                    stiva.pop_back();
                }
                componente[nr_componente].push_back(vecin);
                stiva.pop_back();
                componente[nr_componente].push_back(nod);   // nod ramane si pe stiva
            }
        }
    }
}

int main()
{
    in >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        in >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
    {
        if (nivel[i] == 0)
        {
            nivel[i] = 1;
            dfs(i, 0);
        }
    }
    out << nr_componente << "\n";
    for (int c = 1; c <= nr_componente; c++)
    {
        for (int nod : componente[c])
        {
            out << nod << " ";
        }
        out << "\n";
    }
    return 0;
}