Cod sursa(job #3374600)

Utilizator darius_cimbruDarius Cimbru darius_cimbru Data 9 noiembrie 2026 03:36:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.94 kb
#include <bits/stdc++.h>
#define N 100001
using namespace std;

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

vector<int> vecini[N];
int idx[N]; //al catelea nod vizitat in dfs, 0 = nevizitat
int low[N]; // cel mai mic idx la care ajunge nodul
int urmatorul[N]; // urmatorul[x] = ca la ctc la al catelea vecin al lui x urmeaza sa ma uit
int parinte[N];
vector<int> stiva; // nodurile din componenta care se construieste
vector<vector<int>> componente;
vector<int> componenta;
deque<int> d;
int contor;

int main()
{
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
    for (int radacina = 1; radacina <= n; radacina++)
    {
        if (idx[radacina] != 0)
            continue;
        contor++;
        idx[radacina] = low[radacina] = contor;
        stiva.clear();
        stiva.push_back(radacina);
        d.push_back(radacina);
        while (!d.empty())
        {
            int nod_curent = d.back();
            if (urmatorul[nod_curent] < vecini[nod_curent].size())
            {
                int vecin = vecini[nod_curent][urmatorul[nod_curent]];
                urmatorul[nod_curent]++;
                if (vecin == parinte[nod_curent])
                    continue;
                if (idx[vecin] != 0) // muchie de intoarcere
                    low[nod_curent] = min(low[nod_curent], idx[vecin]);
                else // nevizitat, cobor in el
                {
                    parinte[vecin] = nod_curent;
                    contor++;
                    idx[vecin] = low[vecin] = contor;
                    stiva.push_back(vecin);
                    d.push_back(vecin);
                }
            }
            else // am terminat toti vecinii lui nod_curent
            {
                d.pop_back();
                if (!d.empty()) // ma intorc la parinte
                {
                    int tata = d.back();
                    low[tata] = min(low[tata], low[nod_curent]);
                    if (low[nod_curent] >= idx[tata]) // nod_curent nu poate urca mai sus de tata, deci s-a inchis o componenta
                    {
                        componenta.clear();
                        int nod;
                        do
                        {
                            nod = stiva.back();
                            stiva.pop_back();
                            componenta.push_back(nod);
                        } while (nod != nod_curent);
                        componenta.push_back(tata); // tata ramane pe stiva, poate fi si in alte componente
                        componente.push_back(componenta);
                    }
                }
            }
        }
    }
    g << componente.size() << "\n";
    for (int i = 0; i < componente.size(); i++)
    {
        for (int j = 0; j < componente[i].size(); j++)
            g << componente[i][j] << " ";
        g << "\n";
    }
    f.close();
    g.close();
}