Cod sursa(job #3194584)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 18 ianuarie 2024 17:55:37
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
const int NMAX = 100002;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

int depth[NMAX], low[NMAX];
vector < vector < int > > v, biconexe;
stack < int > s; ///nodurile vizitate in dfs IN ORDINE

void dfs(int nod, int parent, int adancime) {
    s.push(nod);
    depth[nod] = low[nod] = adancime;
    for(auto var : v[nod]) {
        if(var == parent) ///n-are cum sa fie muchie de back
            continue;
        if(depth[var] == -1) { ///nod nevizitat
            dfs(var, nod, adancime + 1);
            low[nod] = min(low[nod], low[var]);

            if(low[var] >= depth[nod]) {
                vector < int > comp; ///salvam in comp componenetele bicon, care sunt deja in stiva
                while(s.top() != var) {
                    comp.push_back(s.top());
                    s.pop();
                }
                comp.push_back(s.top());
                s.pop();
                comp.push_back(nod);
                biconexe.push_back(comp);
            }
        }
        else
            low[nod] = min(low[nod], depth[var]);
    }
}

void init(int n) {
   for(int i = 0; i <= n; i++) {
        depth[i] = -1;
        low[i] = -1;
    }
}

int main()
{
    int n, m, a, b;
    cin >> n >> m;
    init(n);
    v.resize(n + 1);
    for(int i = 1; i <= m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(1, 1, 0);
    cout << biconexe.size() << '\n';
    for(int i = 0; i < biconexe.size(); i++) {
        for(int j = 0; j < biconexe[i].size(); j++)
            cout << biconexe[i][j] << " ";
        cout << '\n';
    }
    return 0;
}