Cod sursa(job #2886952)

Utilizator AswVwsACamburu Luca AswVwsA Data 8 aprilie 2022 17:13:58
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100003;
vector <int> g[NMAX];

int discover[NMAX], low[NMAX], root, nr;
bool art[NMAX];
int tata[NMAX];
stack <int> st;
vector <vector <int> > sol;
void artpoint(int u, int timp)
{
    st.push(u);
    discover[u] = low[u] = timp;
    for (int v : g[u])
        if (discover[v] == 0)
        {
            tata[v] = u;
            artpoint(v, timp + 1);
            if (root == u)
                nr++;
            if (low[v] >= discover[u])
            {
                art[u] = 1;
                sol.push_back({u});
                int top;
                do
                {
                    top = st.top();
                    st.pop();
                    sol[sol.size() - 1].push_back(top);
                }
                while (top != v);
            }
            low[u] = min(low[u], low[v]);
        }
        else if (v != tata[u])
            low[u] = min(low[u], discover[v]);
}
int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n, m, i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    tata[1] = 0;
    artpoint(1, 1);
    cout << sol.size() << "\n";
    for (i = 0; i < sol.size(); i++, cout << "\n")
        for (int j = 0; j < sol[i].size(); j++)
            cout << sol[i][j] << " ";
}