Cod sursa(job #2965955)

Utilizator ptudortudor P ptudor Data 16 ianuarie 2023 16:49:02
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("biconex.in");
ofstream out("biconex.out");
#endif

vector<int> tin,up;
vector<vector<int>> sol,g;
const int inf = 1'000'000'005;

int main() {
    int n,m;
    in >> n >> m;
    tin = vector<int>(n + 1, -1);
    up = vector<int>(n + 1,inf);
    g.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int u,v;
        in >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }    

    int global_tin_time = 0;
    function<void(int,int)> dfs = [&](int node, int parent) {
        tin[node] = ++global_tin_time;
        up[node] = tin[node];
        for (auto k : g[node]) {
            if (tin[k] == -1) {
                dfs(k, node);
                up[node] = min(up[node] , up[k]);
            } else {
                if (k != parent) {
                    up[node] = min(up[node] , tin[k]);
                }
            }
        }
    };

    vector<int> viz(n + 1, 0);
    function<void(int,int)> make_groups = [&](int node, int group_id) {
        sol[group_id].push_back(node);
        viz[node] = 1;  
        for (auto k : g[node]) {
            if (viz[k] == 0) {
                if (up[k] > tin[node]) {
                    sol.push_back({node,k});
                    sol.push_back({});
                    make_groups(k , (int)sol.size() - 1);
                } else {
                    make_groups(k , group_id);
                }
            }
        }
    };
    dfs(1, 0);

    sol.push_back({});
    make_groups(1, 0);

    int nr = 0;
    vector<vector<int>> sol2;
    for (auto k : sol) {
        if (k.size() > 1) {
            sol2.push_back(k);
        }
    }

    out << sol2.size() << "\n";
    
    for (auto k : sol2) {
        for (auto y : k) {
            out << y << " ";
        }
        out << "\n";
    }
}