Cod sursa(job #3374960)

Utilizator merdanovylham03@gmail.comMerdanov Ylham [email protected] Data 9 noiembrie 2026 20:24:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 100005;
vector<int> graf[maxn];
int nivel[maxn], minim[maxn], parinte[maxn], poz[maxn];

int main() {
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    vector<int> st;
    vector<pair<int, int>> muchii;
    vector<vector<int>> componente;
    int timp = 0;
    for (int start = 1; start <= n; start++) {
        if (nivel[start]) continue;
        nivel[start] = minim[start] = ++timp;
        st.push_back(start);
        while (!st.empty()) {
            int u = st.back();
            if (poz[u] < (int)graf[u].size()) {
                int v = graf[u][poz[u]++];
                if (v == parinte[u]) continue;
                if (!nivel[v]) {
                    parinte[v] = u;
                    muchii.push_back({u, v});
                    nivel[v] = minim[v] = ++timp;
                    st.push_back(v);
                } else if (nivel[v] < nivel[u]) {
                    minim[u] = min(minim[u], nivel[v]);
                    muchii.push_back({u, v});
                }
            } else {
                st.pop_back();
                int p = parinte[u];
                if (p) {
                    minim[p] = min(minim[p], minim[u]);
                    if (minim[u] >= nivel[p]) {
                        vector<int> comp;
                        while (!muchii.empty()) {
                            auto e = muchii.back();
                            muchii.pop_back();
                            comp.push_back(e.first);
                            comp.push_back(e.second);
                            if (e.first == p && e.second == u) break;
                        }
                        sort(comp.begin(), comp.end());
                        comp.erase(unique(comp.begin(), comp.end()), comp.end());
                        componente.push_back(comp);
                    }
                }
            }
        }
    }
    fout << componente.size() << '\n';
    for (auto comp : componente) {
        for (int x : comp) fout << x << ' ';
        fout << '\n';
    }
    return 0;
}