Cod sursa(job #3374254)

Utilizator bexxRebeca N bexx Data 8 noiembrie 2026 21:20:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

int cnt, n, m, c;
vector<int>disc,low;
vector<vector<int>>g, comp;
stack<int>s;

void graph() {
    cin>>n>>m;
    g.resize(n+1);
    disc.resize(n+1,0);
    low.resize(n+1,1e5+5);
    int x,y;
    for (int i=0;i<m;i++) {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void dfs(int node, int parent) {
    cnt++;
    disc[node]=low[node]=cnt;
    s.push(node);
    for (int v:g[node]) {
        if (v==parent)
            continue;
        if (disc[v])
            low[node]=min(low[node],disc[v]);
        else{
            dfs(v,node);
            low[node]=min(low[node],low[v]);
            if (low[v]>=disc[node]) {
                comp.push_back({});
                while (!s.empty() && s.top()!=v ) {
                    comp[c].push_back(s.top());
                    s.pop();
                }
                comp[c].push_back(s.top());
                s.pop();
                comp[c].push_back(node);
                c++;
            }
        }
    }

}

int main() {
    graph();
    for (int node=1;node<=n;node++)
        if (!disc[node])
            dfs(node, 0);
    cout<<comp.size()<<'\n';
    for (int i=0; i<comp.size();i++,cout<<'\n')
        for (int node:comp[i])
            cout<<node<<' ';
    return 0;
}