Cod sursa(job #3374243)

Utilizator TomikeToma Rares Tomike Data 8 noiembrie 2026 21:09:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
using namespace std;

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

int n, m, timp;
vector<int> g[100005];
int disc[100005], low[100005];
vector<int> st;
vector<vector<int>> comp;

void dfs(int u, int tata){
    timp ++;
    disc[u] = low[u] = timp;
    st.push_back(u);
    for(int v : g[u]){
        if(!disc[v]){
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= disc[u]){
                vector<int> c;
                while(true){
                    int x = st.back();
                    st.pop_back();
                    c.push_back(x);
                    if(x == v) break;
                }
                c.push_back(u);
                comp.push_back(c);
            }
        }else if(v != tata){
            low[u] = min(low[u], disc[v]);
        }
        
    }
}

int main(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

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

    fout << comp.size() << endl;
    for(auto &c : comp){
        for(int x : c){
            fout << x << ' ';
        }
        fout << endl;
    }
}