Cod sursa(job #3000883)

Utilizator Vali_nnnValentin Nimigean Vali_nnn Data 13 martie 2023 01:29:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <stack>
#include <vector>
#define MAX 100005

using namespace std;

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

stack <int> stk;

vector <int> v[MAX] , sol[MAX];

int viz[MAX] , niv[MAX] , nivmin[MAX] , comp , n , m , x , y;

void dfs (int nod , int lvl)
{
    viz[nod] = 1;
    niv[nod] = nivmin[nod] = lvl;
    stk.push (nod);
    for (int j=0;j<v[nod].size();j++)
    {int vecin=v[nod][j];
        if (viz[vecin] == 1)
            nivmin[nod] = min(nivmin[nod] , niv[vecin]);
        else
        {
            dfs (vecin , lvl + 1);

            if (niv[nod] <= nivmin[vecin])
            {
                comp++;
                while (stk.top () != vecin)
                {
                    sol[comp].push_back (stk.top ());
                    stk.pop ();
                }
                sol[comp].push_back (stk.top ());
                sol[comp].push_back (nod);
                stk.pop();
            }
            nivmin[nod] = min (nivmin[nod] , nivmin[vecin]);
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1 ; i <= m ; i++)
    {
        f >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }

    dfs (1 , 1);

    g << comp << '\n';

    for (int i = 1 ; i <= comp ; i++)
    {
        for (int j=sol[i].size()-1;j>=0;j--)
            g << sol[i][j]<< " ";
        g << '\n';
    }
    return 0;
}