Cod sursa(job #3287571)

Utilizator GabyXBBabiuc Eduard Gabriel GabyXB Data 18 martie 2025 16:52:25
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

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

const int nmax = 100005;
vector<int> G[nmax] , biconexe[nmax];
///vector<pair<int,int>> sol;
stack<int> stiva;
///set<int> s;
int v[nmax];
int low[nmax] , num[nmax];
int timpulamea , n , m , k;

void citire()
{
    int x , y;
    cin >> n >> m ;
    for(int i = 1 ; i<=m ; ++i)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void dfs(int nod , int rad )
{
    v[nod] = 1;
    low[nod] = num[nod] = ++timpulamea;
    stiva.push(nod);
    for(auto e : G[nod])
        if(e != rad)
        {
            if(!v[e])
            {
                dfs(e,nod);
                if(low[e] <= low[nod])
                    low[nod] = low[e];
                else
                {
                    ///s.insert(nod);
                    ///s.insert(e);
                    ++k;
                    biconexe[k].push_back(nod);
                    biconexe[k].push_back(e);
                    ///sol.push_back({nod,e});
                }
            }
            else if(low[e] <= low[nod])
                    low[nod] = low[e];
        }
    if(low[nod] == num[nod])
    {
        if(stiva.top() != nod && !stiva.empty())
        {
            ++k;
            while(!stiva.empty() && low[stiva.top()] == low[nod])
            {
                biconexe[k].push_back(stiva.top());
                stiva.pop();
            }
        }
        else if(!stiva.empty())
            stiva.pop();
    }
}

void debug()
{
    cout << "****** GRAF ******\n";
    for(int i = 1 ; i<=n ; ++i)
    {
        cout << "Pentru " << i << " : ";
        for(auto e : G[i]) cout << e << ' ';
        cout << '\n';
    }
    cout << "\n\n";
    cout << "****** BICONEXE ******\n";
    for(int i = 1 ; i<=k ; ++i)
    {
        cout << "Pentru " << i << " : ";
        for(auto e : biconexe[i]) cout << e << ' ';
        cout << '\n';
    }
}

int main()
{
    citire();
    for(int i = 1 ; i<=n ; ++i)
        if(!v[i])
        dfs(i,0);
    ///debug();
    cout << k << '\n';
    for(int i = 1 ; i<=k ; ++i)
    {
        for(auto e : biconexe[i]) cout << e << ' ';
        cout << '\n';
    }
}