Cod sursa(job #3336277)

Utilizator voaidesrVoaides Robert voaidesr Data 24 ianuarie 2026 14:58:40
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

vector<vector<int>> adj, comps;
vector<bool> vis;
vector<int> tin, tmin;
stack<pair<int, int>> edges;
int timer;

void dfs(int u, int p = -1) {
    vis[u] = true;
    tin[u] = tmin[u] = timer++;

    for (int v : adj[u]) {
        if (v == p) continue;

        if (vis[v]) {
            if (tin[v] < tin[u])
                edges.push({u, v});
            tmin[u] = min(tmin[u], tin[v]);
        }
        else {
            edges.push({u, v});
            dfs(v, u);
            tmin[u] = min(tmin[u], tmin[v]);

            if (tmin[v] >= tin[u]) { // punct critic
                vector<int> curr_comp;
                set<int> nodes;
                pair<int, int> edge = {0, 0};

                while (edge.first != u ||edge.second != v) {
                    edge = edges.top();
                    edges.pop();

                    nodes.insert(edge.first);
                    nodes.insert(edge.second);
                }

                for (int nd : nodes)
                    curr_comp.push_back(nd);

                comps.push_back(curr_comp);
            }
        }
    }
}

int main() {
    timer = 0;
    int n, m;
    cin >> n >> m;

    adj.assign(n + 1, vector<int>());
    vis.assign(n + 1, false);
    tin.assign(n + 1, -1);
    tmin.assign(n + 1, -1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1);

    cout << comps.size() << "\n";

    for (auto comp : comps) {
        for (int elem : comp)
            cout << elem << " ";
        cout << "\n";
    }

    return 0;
}