Cod sursa(job #3299570)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 8 iunie 2025 15:36:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in  fin
#define out fout

using namespace std;

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

int niv[100001], h[100001];
vector<int> g[100001];
bool m[100001];
stack<int> s;
vector< vector<int> > comp;

void build(int nod){
    m[nod] = 1;
    s.push(nod);
    for(const int &x : g[nod]){
        if(m[x]){
            h[nod] = min(h[nod], niv[x]); // muchie de intoarcere
            continue;
        }
        niv[x] = h[x] = niv[nod] + 1;
        build(x);
        h[nod] = min(h[nod], h[x]);

        if(h[x] >= niv[nod]){
            // cout << "Este componenta de la " << nod << " ---> " << x << '\n';
            comp.push_back({});
            while(s.top() != x){
                comp.back().push_back(s.top());
                s.pop();
            }
            comp.back().push_back(s.top()); s.pop();
            comp.back().push_back(nod);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n, m; in >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; in >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    niv[1] = h[1] = 1;
    build(1);

    // cout << "h   : ";
    // for(int i = 1; i <= n; i++) cout << h[i] << " ";
    // cout << '\n';
    // cout << "niv : ";
    // for(int i = 1; i <= n; i++) cout << niv[i] << " ";
    // cout << '\n';

    out << comp.size() << '\n';
    for(const vector<int> &i : comp){
        for(const int &x : i) out << x << " ";
        out << '\n';
    }

    return 0;
}