Cod sursa(job #2981175)

Utilizator Elvis_CostinTuca Elvis-Costin Elvis_Costin Data 17 februarie 2023 14:25:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
#include <bits/stdc++.h>
using namespace std;
string np = "biconex";
ifstream f(np + ".in");
ofstream g(np + ".out");

// #define f cin
// #define g cout

int n, m, radacina, t[100003], nivel[100003], nma[100003];
bool viz[100003], p_art[100003];
vector<int> adj[100003];
vector<pair<int, int>> punti;
vector<vector<int>> comp_bicon;
stack<int> st;

void dfs(int nod, int tata)
{
    viz[nod] = 1;
    nivel[nod] = nma[nod] = nivel[tata] + 1;
    st.push(nod); // pt det comp biconex
    int nrfii = 0;
    for (auto next : adj[nod])
        if (next != tata)
        {
            if (viz[next])
                nma[nod] = min(nma[nod], nivel[next]);
            else
            {
                nrfii++;
                dfs(next, nod);
                nma[nod] = min(nma[nod], nma[next]);

                // det punti
                if (nivel[nod] < nma[next])
                    punti.push_back({nod, next});

                if (nivel[nod] <= nma[next])
                {
                    // det puncte articulatie
                    if (nod != radacina)
                        p_art[nod] = 1;

                    // det componente biconexe
                    vector<int> aux;
                    while (st.top() != next)
                        aux.push_back(st.top()), st.pop();
                    aux.push_back(next);
                    st.pop();
                    aux.push_back(nod);
                    comp_bicon.push_back(aux);
                }
            }
        }
    if (nod == radacina and nrfii > 1)
        p_art[nod] = 1;
}
int main()
{
    // f >> cer;
    f >> n >> m;
    for (int i = 1, a, b; i <= m; i++)
        f >> a >> b,
            adj[a].push_back(b), adj[b].push_back(a);

    radacina = 1;
    dfs(1, 0);

    // if (cer == 1)
    // {
    g << comp_bicon.size() << '\n';
    for (int i = 0; i < comp_bicon.size(); i++, g << '\n')
    {
        // g << comp_bicon[i].size() << " ";
        for (auto x : comp_bicon[i])
            g << x << " ";
    }
    // }
    // else if (cer == 2)
    // {
    //     int rez = 0;
    //     for (int i = 1; i <= n; i++)
    //         if (p_art[i] == 1)
    //             rez++;
    //     g << rez << '\n';
    //     for (int i = 1; i <= n; i++)
    //         if (p_art[i] == 1)
    //             g << i << " ";
    // }
    // else
    // {
    //     g << punti.size() << '\n';
    //     for (auto x : punti)
    //         g << x.first << " " << x.second << '\n';
    // }

    return 0;
}