Cod sursa(job #3004212)

Utilizator RobertlelRobert Robertlel Data 16 martie 2023 10:37:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#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 nivel)
{
    viz[nod] = 1;
    niv[nod] = nivmin[nod] = nivel;
    stk.push (nod);
    for (int i = 0 ; i < v[nod].size() ; i++)
    {
        int vecin = v[nod][i];
        if (viz[vecin] == 1)
            nivmin[nod] = min (niv[vecin] , nivmin[nod]);
            else
            {

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


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 (auto j : sol[i])
            g << j << " ";
        g << '\n';
    }
    return 0;
}