Cod sursa(job #2886879)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 8 aprilie 2022 15:42:38
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>

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

int const NMAX = 100000;
std::vector<int> G[NMAX + 5];
int p[NMAX + 5];
int depth[NMAX + 5];
int low[NMAX + 5];

std::vector<std::vector<int>> comp;
int compCount = 0;

std::stack<int> st;

void dfs (int nod, int currDepth) {
    depth[nod] = currDepth;
    low[nod] = depth[nod];
    st.push(nod);

    for (auto x : G[nod]) {
        if (depth[x] == 0) {
            p[x] = nod;
            dfs(x, currDepth + 1);
            if (low[x] >= depth[nod]) {
                comp.push_back({}); compCount++;
                int top;
                do {
                    top = st.top();
                    st.pop();
                    comp[compCount - 1].push_back(top);
                } while (top != nod);
                st.push(nod);
            }
            low[nod] = std::min(low[nod], low[x]);
        } else if (x != p[nod])
            low[nod] = std::min(low[nod], low[x]);
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    p[1] = 0;
    dfs (1, 1);
    fout << compCount << "\n";
    for (int i = 0; i < compCount; i++) {
        int size = comp[i].size();
        for (int j = 0; j < size; j++)
            fout << comp[i][j] << " ";
        fout << "\n";
    }
    return 0;
}