Cod sursa(job #3296114)

Utilizator paulihno15Ciumandru Paul paulihno15 Data 11 mai 2025 16:21:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>
#define NMAX 100000

using namespace std;

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

int cer, n, m, a, b;
int cnt_comp_biconexe;
vector<int> graf[NMAX + 2];
stack<int> st;
vector<vector<int>> comp_biconexe;
bool viz[NMAX + 2];
int niv[NMAX + 2], low[NMAX + 2];

void DFS(int nod, int par) {
    viz[nod] = 1;
    niv[nod] = low[nod] = niv[par] + 1;
    st.push(nod);
    int fii = 0;

    for (int vec : graf[nod]) {
        if (vec == par) {
            continue;
        }
        if (viz[vec]) {
            low[nod] = min(niv[vec], low[nod]);
        }
        else {
            fii++;
            DFS(vec, nod);
            low[nod] = min(low[vec], low[nod]);

            if (low[vec] >= niv[nod]) {
                comp_biconexe.emplace_back(vector<int>(0));

                int x;
                do {
                    x = st.top();
                    st.pop();
                    comp_biconexe[cnt_comp_biconexe].emplace_back(x);
                } while (x != vec);
                comp_biconexe[cnt_comp_biconexe].emplace_back(nod);
                cnt_comp_biconexe++;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n >> m;
    while (m--) {
        fin >> a >> b;
        graf[a].emplace_back(b);
        graf[b].emplace_back(a);
    }

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

    fout << cnt_comp_biconexe << '\n';
    for (int i = 0; i < cnt_comp_biconexe; i++) {
        for (int j = 0; j < comp_biconexe[i].size(); j++) {
            fout << comp_biconexe[i][j] << ' ';
        }
        fout << '\n';
    }
    return 0;
}