Cod sursa(job #2909636)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 14 iunie 2022 13:21:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int N = 1e5;
vector <int> g[N + 1];
vector < vector <int> > ras;

int low[N + 1], discover[N + 1], tata[N + 1];

stack <int> s;

int n, m, nod1, nod2;

void artic(int nod, int timp)
{
    s.push(nod);
    discover[nod] = low[nod] = timp;
    for (auto it : g[nod])
    {
        if (!discover[it])
        {
            tata[it] = nod;
            artic(it, timp + 1);
            if (low[it] >= discover[nod])
            {
                ras.push_back({nod});
                int top;
                while (top != it)
                {
                    top = s.top();
                    s.pop();
                    ras[ras.size() - 1].push_back(top);
                }
            }
            low[nod] = min (low[nod], low[it]);
        }
        else if (it != tata[nod])
            low[nod] = min (low[nod], discover[it]);
    }


}
int main()
{
    for (cin >> n >> m; m; --m)
    {
        cin >> nod1 >> nod2;
        g[nod1].push_back(nod2);
        g[nod2].push_back(nod1);
    }
    artic(1, 1);
    cout << ras.size() << '\n';
    for (int i = 0; i < ras.size(); ++i, cout << '\n')
        for (int j = 0; j < ras[i].size(); ++j)
            cout << ras[i][j] << ' ';
    return 0;
}