Cod sursa(job #2966045)

Utilizator ptudortudor P ptudor Data 16 ianuarie 2023 18:13:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 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, int)> make_groups = [&](int node, int group_id, int top) {
        sol[group_id].push_back(node);
        viz[node] = 1;  
        for (auto k : g[node]) {
            if (viz[k] == 0) {
                if ((top == node && up[k] > tin[node]) || (top != node && up[k] >= tin[node])) { /// is an articulation point
                    sol.push_back({node});
                    make_groups(k , (int)sol.size() - 1, node);
                } else {
                    make_groups(k , group_id, top);
                }
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        if (tin[i] == -1) {
            dfs(i, 0);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (tin[i] == -1) {
            cout << "nope : " << i << "\n";
        }
    }

    for (int i = 1; i <= n; i++) {
        if (viz[i] == 0) {
            sol.push_back({});
            make_groups(i, (int)sol.size() - 1, i);
        }
    }
    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";
    }
}