Cod sursa(job #3242426)

Utilizator susanSusan Ssssss susan Data 12 septembrie 2024 09:25:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <functional>
#include <vector>
#include <stack>

using namespace std;

int main() {
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    int n, m, cnt = 0;
    f >> n >> m;

    vector<vector<int> > adj(n), sol(n);
    vector<bool> vis(n);
    vector<int> niv(n), low(n);

    while (m--) {
        int u, v;
        f >> u >> v;
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }

    stack<int> S;

    function<void(int, int)> dfs = [&](const int u, const int p) {
        vis[u] = true;
        low[u] = niv[u];
        S.push(u);

        for (const auto &v: adj[u]) {
            if (v == p)
                continue;

            if (vis[v]) {
                low[u] = min(low[u], niv[v]);
                continue;
            }

            niv[v] = niv[u] + 1;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= niv[u]) {
                ++cnt;
                do {
                    sol[cnt].push_back(S.top());
                    S.pop();
                } while (!S.empty() && sol[cnt].back() != v);
                sol[cnt].push_back(u);
            }
        }
    };

    dfs(0, -1);

    g << cnt << '\n';

    for (int i = 1; i <= cnt; ++i) {
        for (const auto &it: sol[i])
            g << it + 1 << ' ';
        g << '\n';
    }
}