Cod sursa(job #2542106)

Utilizator BluThund3rRadu George BluThund3r Data 9 februarie 2020 14:54:22
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;

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

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

int n, m, nocomp;

static inline void addsolution(int x, int y, int comp)
{
    while(true)
    {
        int fir = stiva.top().first;
        int sec = stiva.top().second;
        stiva.pop();

        solution[nocomp].push_back(fir);
        solution[nocomp].push_back(sec);

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

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

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

    for(auto i : adj[nod])
    {
        if(i == parent)
            continue;

        if(!niv[i])
            {
                stiva.push({nod, i});
                dfs(i, nod, lvl + 1);

                low[nod] = min(low[nod], low[i]);

                if(niv[nod] <= low[i])
                {
                    ++ nocomp;
                    addsolution(nod, i, nocomp);
                }
            }

        else
            low[nod] = min(low[nod], niv[i]);
    }
}

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);

    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;
}