Cod sursa(job #3293938)

Utilizator LuciBBadea Lucian LuciB Data 13 aprilie 2025 20:50:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1e5;

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

vector<int> graph[NMAX];
int depth[NMAX], low[NMAX];

bool vis[NMAX];

vector<int> stiva;
vector<vector<int>> bcc;

void pushBcc(int u, int v) {
    vector<int> comp;
    while(stiva.back() != v) {
        comp.push_back(stiva.back());
        stiva.pop_back();
    }
    comp.push_back(v);
    comp.push_back(u);
    stiva.pop_back();
    bcc.push_back(comp);
}


void dfs(int node, int parent) {
    static int time = 0;
    depth[node] = low[node] = ++time;
    stiva.push_back(node);
    for(auto x : graph[node]) {
        if(depth[x] == 0) {
            dfs(x, node);
            low[node] = min(low[node], low[x]);
            if(low[x] >= depth[node]) {
                pushBcc(node, x);
            }
        } else if(x != parent) {
            if(depth[x] < depth[node]) {
                low[node] = min(low[node], depth[x]);
            }
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(0, -1);
    fout << bcc.size() << '\n';
    for(auto comp : bcc) {
        for(auto x : comp) {
            fout << x + 1 << ' ';
        }
        fout << '\n';
    }
    return 0;
}