Cod sursa(job #3372278)

Utilizator ursus161Stefan Ghetu ursus161 Data 2 noiembrie 2026 22:52:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> g[N], st;
vector<vector<int>> comps;
int d[N], low[N], timp;

void dfs(int u) {
    d[u] = low[u] = ++timp;
    st.push_back(u);
    for (int v : g[u]) {
        if (d[v]) { low[u] = min(low[u], d[v]); continue; }
        dfs(v);
        low[u] = min(low[u], low[v]);
        if (low[v] >= d[u]) {
            comps.push_back({u});
            int x;
            do { 
            x = st.back(); 
                
            st.pop_back(); comps.back().push_back(x); } 
            while (x != v);
        }
    }
}

int main() {
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n, m; fin >> n >> m;

    while (m--) { 
        int x, y; fin >> x >> y; 
        
        g[x].push_back(y); g[y].push_back(x);
     }
    for (int i = 1; i <= n; i++)
     if (!d[i]) { dfs(i); st.clear(); }

    fout << comps.size() << "\n";
    for (auto& c : comps) { for (int x : c) fout << x << " "; fout << "\n"; }
}