Cod sursa(job #3374666)

Utilizator fanceapaMosul Tudor fanceapa Data 9 noiembrie 2026 08:54:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout("biconex.out");

vector < vector <int> > muchii, componente;
vector <int> nivel, low, stiva;
int timp = 0;

void dfs(int nod, int tata){
    nivel[nod] = low[nod] = ++timp;
    stiva.push_back(nod);
    for (auto vecin : muchii[nod]){
        if (vecin == tata){
            continue;
        }
        if (nivel[vecin] == 0){
            dfs(vecin, nod);
            low[nod] = min(low[nod], low[vecin]);
            if (low[vecin] >= nivel[nod]){
                vector <int> componenta;
                while (stiva.back() != vecin){
                    componenta.push_back(stiva.back());
                    stiva.pop_back();
                }
                componenta.push_back(vecin);
                stiva.pop_back();
                componenta.push_back(nod);
                componente.push_back(componenta);
            }
        }
        else{
            low[nod] = min(low[nod], nivel[vecin]);
        }
    }
}

int main(){
    int N, M;
    fin >> N >> M;
    muchii.resize(N + 1);
    nivel.resize(N + 1, 0);
    low.resize(N + 1, 0);
    for (int i = 0; i < M; i++){
        int x, y;
        fin >> x >> y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }

    for (int i = 1; i <= N; i++){
        if (nivel[i] == 0){
            dfs(i, 0);
            stiva.clear();
        }
    }

    fout << componente.size() << "\n";
    for (int i = 0; i < componente.size(); i++){
        for (auto nod : componente[i]){
            fout << nod << " ";
        }
        fout << "\n";
    }
    return 0;
}