Cod sursa(job #3371819)

Utilizator StefanAlexandru1914Petcovici StefanAlexandru1914 Data 31 octombrie 2026 22:11:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int n, m;
vector<vector<int>> adj;
vector<vector<int>> comp;
stack<int> st;
vector<int> viz;
vector<int> nivel;
vector<int> low; // cel mai mic nivel la care se poate intoarce un nod
int timer, nr_comp;

void DFS(int nod, int parinte) {
    timer++;
    nivel[nod] = timer;
    low[nod] = nivel[nod];
    viz[nod] = 1;
    st.push(nod);
    int ramuri = 0;
    for (int i : adj[nod]) {
        if (!viz[i]) {
            ramuri++;
            DFS(i, nod);
            low[nod] = min(low[nod], low[i]);
            if (nivel[nod] <= low[i]) {
                vector<int> comp_crt;
                int aux;
                do {
                    aux = st.top();
                    st.pop();
                    comp_crt.push_back(aux);

                } while (aux != i);
                comp_crt.push_back(nod);
                comp.push_back(comp_crt);
            }

        }
        else if (i != parinte) {
            low[nod] = min(low[nod], nivel[i]);
        }
    }
}

int main()
{
    fin >> n >> m;
    adj.resize(n + 5);
    viz.resize(n + 5);
    nivel.resize(n + 5);
    low.resize(n + 5);
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (!viz[i]) {
            DFS(i,0);
        }
    fout << comp.size() << '\n';
    for (auto& c : comp) {
        for (int i : c)
            fout << i << " ";
        fout << '\n';
    }
    return 0;
}