Cod sursa(job #2884018)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 2 aprilie 2022 11:08:02
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int NMAX = 1e5 + 5;
vector <int> g[NMAX];
int n, m, niv[NMAX], nivmin[NMAX];

void citire()
{
    fin >> n >> m;

    int i, j, a, b;
    for(i = 1; i <= m; ++i)
    {
        fin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
}

bitset <NMAX> viz;
stack <int> stiva;
vector < vector <int> > sol;
vector <int> ax;

void dfs(int node, int fadir)
{
    stiva.push(node);
    viz[node] = 1;
    nivmin[node] = niv[node] = niv[fadir] + 1;

    for(auto &it: g[node])
    {
        if(it == fadir) continue;

        if(viz[it]) {
            nivmin[node] = min(nivmin[node], nivmin[it]);
            continue;
        }

        dfs(it, node);
        nivmin[node] = min(nivmin[node], nivmin[it]);

        //nu pot merge mai sus, am componenta biconexa
        if(nivmin[it] >= niv[node])
        {
            ax.clear();
            while(!stiva.empty() && stiva.top() != it)
            {
                ax.push_back(stiva.top());
                stiva.pop();
            }

            if(!stiva.empty() && stiva.top() == it)
            {
                ax.push_back(stiva.top());
                stiva.pop();
            }

            ax.push_back(node);
            sort(ax.begin(), ax.end());
            sol.push_back(ax);
        }
    }
}

int main()
{
    citire();
    dfs(1, 0);

       fout << sol.size() << '\n';

       for(auto &it: sol)
       {
           for(auto &it2: it)
                fout << it2 << ' ';
           fout << '\n';
       }

    return 0;
}