Cod sursa(job #3374091)

Utilizator laur7766laur m laur7766 Data 8 noiembrie 2026 17:34:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, M, bconex;
int vizitat[100005];
vector<int> G[100005];
stack<int> S;
vector<vector<int>> comp_biconex;

int niv[100005], niv_min[100005];

void DFS(int Nod, int Tata) {
    vizitat[Nod] = 1;
    
    // actualizam nivelele
    niv[Nod] = niv[Tata] + 1;
    niv_min[Nod] = niv[Nod];
    
    S.push(Nod);

    for (auto vecin : G[Nod]) {
        if (vecin == Tata) continue;

        if (!vizitat[vecin]) {
            DFS(vecin, Nod);

            // cand ne intoarcem din fiu actualizam niv_min pentru Nod
            niv_min[Nod] = min(niv_min[Nod], niv_min[vecin]);

            // daca Nod nu e radacina si subarborele fiului nu poate urca mai sus de Nod
            // e nod critic / punct de articulatie
            if (niv_min[vecin] >= niv[Nod]) {
                vector<int> bcomp;
                while (!S.empty() && S.top() != vecin) {
                    bcomp.push_back(S.top());
                    S.pop();
                }
                bcomp.push_back(vecin);
                S.pop();

                // Nod intra in componenta, dar ramane pe stiva
                bcomp.push_back(Nod); 
                comp_biconex.push_back(bcomp);
            }
        }
        else {
            // verificam si actualizam niv_min[Nod]
            // in cazul in care putem ajunge la un nod deja vizitat (muchie de intoarcere)
            niv_min[Nod] = min(niv_min[Nod], niv[vecin]);
        }
    }
}

int main() {
    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);
    }

    for (int i = 1; i <= N; ++i) {
        if (vizitat[i] == 0) {
            DFS(i, 0);
        }
        while(!S.empty()) S.pop();
    }
    
    fout << comp_biconex.size() << '\n';
    for(auto& compi : comp_biconex) {
        sort(compi.begin(), compi.end());
        for(auto elem : compi) {
            fout << elem << ' ';
        }
        fout << '\n';
    }
    
    return 0;
}