Cod sursa(job #3372573)

Utilizator ananicoletaRosca Ana-Nicoleta ananicoleta Data 4 noiembrie 2026 12:14:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int MAXN = 100005;
int n,m,timer;
vector<vector<int>> adj;
vector<int> low(MAXN);
vector<int> dfn(MAXN);
stack<int> stiva;
vector<vector<int>> componente;

void dfs(int current, int parent) {
    dfn[current]= low[current] = ++timer;
    stiva.push(current);
    for (int vecin : adj[current]) {
        if (vecin==parent) continue;
        if (dfn[vecin]) { //a mai fost vizitat si doar preia min
            low[current] = min(low[current], dfn[vecin]);
        } else {
            dfs(vecin,current);
            low[current]=min(low[current],low[vecin]);

            if (low[vecin]>=dfn[current]) {
                vector<int> comp;
                comp.push_back(current);
                while (true) {
                    int node=stiva.top();
                    stiva.pop();
                    comp.push_back(node);
                    if (node==vecin) break;
                }
                componente.push_back(comp);
            }
        }
    }

}

int main() {
    fin>>n>>m;
    adj.assign(n + 1, vector<int>());
    for (int i=0;i<m;i++) {
        int a,b;
        fin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i=1;i<=n;i++) {
        if (!dfn[i]) {
            dfs(i,0);
        }
    }

    fout<<componente.size()<<"\n";
    for (const auto& comp : componente) {
        for (int node : comp) {
            fout << node << " ";
        }
        fout << "\n";
    }
    return 0;
}