Cod sursa(job #3371330)

Utilizator natalia_denisa14Natalia natalia_denisa14 Data 29 octombrie 2026 19:29:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m,x,y,lvl[nmax], low[nmax],nr_comp,timp;
bool viz[nmax];
stack<int> s;
vector<int> adj[nmax],cbc[nmax];

void dfs(int nod, int tata) {
    viz[nod]=1;
    timp++;
    lvl[nod]=low[nod]=timp;
    s.push(nod);

    for (int j=0;j<adj[nod].size();j++) {
        int vecin=adj[nod][j];
        if (vecin==tata) continue;
        if (viz[vecin]==1) {
            low[nod]=min(lvl[vecin], low[nod]);
        }
        else if (!viz[vecin]) {
            dfs(vecin,nod);
            low[nod]=min(low[vecin], low[nod]);

            if (low[vecin]>=lvl[nod]) {
                cbc[nr_comp].push_back(nod);
                while (s.top()!=vecin) {
                    cbc[nr_comp].push_back(s.top());
                    s.pop();
                }
                cbc[nr_comp].push_back(s.top()); s.pop();
                nr_comp++;
            }
        }
    }
}
int main() {
    f>>n>>m;
    for (int i=1;i<=m;i++) {
        f>>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);
        }
    }
    g<<nr_comp<<'\n';
    for (int i=0;i<nr_comp;i++) {
        for (int j=0;j<cbc[i].size();j++)
            g<<cbc[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}