Cod sursa(job #2971688)

Utilizator ptudortudor P ptudor Data 27 ianuarie 2023 20:17:35
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 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

const int NMAX = 45005;
vector<vector<int>> g;
int n,m,s,e,q,needed[NMAX],tin[NMAX],low[NMAX],timer,articulation[NMAX],viz[NMAX];
void dfs(int node, int parent = 0) {
    tin[node] = ++timer;
    int kids = 0;
    low[node] = tin[node];
    for (auto k : g[node]) {
        if (k == parent) {
            continue;
        }

        if (tin[k] == 0) {
            kids++;
            dfs(k, node);
            if (low[k] >= tin[node]) {
                articulation[node] = 1;
            }
            low[node] = min(low[node] , low[k]);
        }  else {
            low[node] = min(low[node] , tin[k]);
        }
    }
    if (parent == 0) {
        articulation[node] = kids > 1;
    } 
}
vector<vector<int>> comps;
void get_comps(int node, int id) {
    viz[node] = 1;
    comps[id].push_back(node);
    for (auto k : g[node]) {
        if (viz[k] == 0) {
            if (articulation[k] == 0) {
                get_comps(k , id);
            } else {
                comps.push_back({});
                get_comps(k , (int)comps.size() - 1);
            }
        }
    }
}
int main() {
    in >> n >> m;
    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);
    }
    in >> s >> e >> q;
    dfs(s);
    comps.push_back({});
    get_comps(1 , 0);

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