Cod sursa(job #2540107)

Utilizator BluThund3rRadu George BluThund3r Data 6 februarie 2020 19:06:18
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <bits/stdc++.h>
using namespace std;

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

const int Nmax = 10e5 + 5;
typedef pair <int, int> ipair;
vector <int> adj[Nmax], solution[Nmax], niv, low;
stack <ipair> stiva;

int n, m, nocomp;

static inline void addsolution(int x, int y)
{
    while(true)
    {
        int fir = stiva.top().first;
        int sec = stiva.top().second;
        solution[nocomp].push_back(fir);
        solution[nocomp].push_back(sec);
        stiva.pop();

        if(fir == x && sec == y)
            break;
    }

    sort(solution[nocomp].begin(), solution[nocomp].end());
}

static inline void dfs(int nod, int parent, int lvl)
{
    niv[nod] = low[nod] = lvl;

    for(auto i : adj[nod])
    {
        if(i == parent) // daca nodul urmator este tatal nodului curent
            continue; // treci mai departe

        if(!low[i]) // daca nodul urmator nu a fost vizitat inca
            {
                stiva.push({nod, i}); // adaug pe stiva muchia care face parte din componenta biconexa componenta biconexa
                dfs(i, nod, lvl + 1); // continui cu dfs din nodul urmator

                low[nod] = min(low[nod], low[i]); // nivelul minim la care se poate ajunge din nodul curent prin descendenti

                if(niv[nod] <= low[i]) // daca nici un descendent al nodului curent nu poate ajunge mai sus de el
                {
                    ++ nocomp; // creste numarul componentelor biconexe
                    addsolution(nod, i); // adaug solutia
                }

            }

        else                                  // daca nodul urmator a fost vizitat anterior
            low[nod] = min(low[nod], niv[i]); // gasesc nivelul minim la care pot ajunge din nodul meu curent prin toti descendentii lui
    }
}

void output()
{
    out << nocomp << '\n';

    for(auto i = 1; i <= nocomp; ++ i)
    {
        for(auto& j : solution[i])
            if(*(&j + 1) != j)
                out << j << ' ';
        out << '\n';
    }
}

int main()
{
    in.tie(0);
    in >> n >> m;

    niv.resize(n + 1);
    low.resize(n + 1, 0);

    while(m --)
    {
        int x, y;
        in >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(1, 0, 1);

    output();

    return 0;
}