Cod sursa(job #3375037)

Utilizator pokeChircu Andrei-Denis poke Data 9 noiembrie 2026 23:31:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <algorithm>

std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");

std::vector<std::vector<int>> biconexe;
std::vector<int> vasdf[100001], st;
int disc[100001], low[100001];
bool viz[100001];
int timer;

void dfs(int nod, int par) {
    viz[nod] = true;
    disc[nod] = low[nod] = ++timer;
    st.push_back(nod);

    for (int vecin : vasdf[nod])
        if (vecin != par)
            if (viz[vecin])
                low[nod] = std::min(low[nod], disc[vecin]);
            else {
                dfs(vecin, nod);
                low[nod] = std::min(low[nod], low[vecin]);
                if (low[vecin] >= disc[nod]) {
                    std::vector<int> comp;
                    while (true) {
                        int n = st.back();
                        st.pop_back();
                        comp.push_back(n);
                        if (n == vecin)
                            break;
                    }
                    comp.push_back(nod);
                    biconexe.push_back(comp);
                }
            }
}

int main() {
    int n, m;
    fin >> n >> m;

    int x, y;
    for (int i = 0; i < m; i++) {
        fin >> x >> y;
        vasdf[x].push_back(y);
        vasdf[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i, 0);

    fout << biconexe.size() << std::endl;
    for (auto comp : biconexe) {
        for (int nod : comp)
            fout << nod << " ";
        fout << std::endl;
    }
    return 0;
}