Cod sursa(job #3372608)

Utilizator maria_avramAvram Maria Teodora maria_avram Data 4 noiembrie 2026 13:29:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb

#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <algorithm>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int timp;
constexpr int NMAX = 100005;
vector<vector<int>>graph, bccs;
stack<int> st;
int disc[NMAX];
int low[NMAX];
void dfs(int node, int parent)
{
    disc[node] = low[node] = ++timp;
    st.push(node);
    for(int next:graph[node])
        if(next == parent) continue;
        else if(disc[next] == 0) {
            dfs(next, node);
            low[node] = min(low[node], low[next]);
            if (low[next] >= disc[node]) {
                vector<int> bcc_noua;
                int extras;
                do {
                    extras = st.top();
                    bcc_noua.push_back(extras);
                    st.pop();

                }while (extras != next);
                bcc_noua.push_back(node);
                bccs.push_back(bcc_noua);
            }
        }
        else
            low[node] = min(low[node], disc[next]);

}
int main() {
    int n,m;
    f >> n >> m;
    graph.assign(n + 1,vector<int>());
    for(int i=1; i<=m; i++)
    {
        int x, y;
        f>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(disc[i] == 0)
        {
            dfs(i, 0);
        }
    g << bccs.size() << '\n';

    for (auto bcc : bccs) {
        for (auto node : bcc) {
            g << node << ' ';
        }
        g << '\n';
    }
    return 0;
}