Cod sursa(job #3306008)

Utilizator radustn92Radu Stancu radustn92 Data 6 august 2025 16:02:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int N, M;
vector<vector<int>> graph;
vector<int> low, level;
vector<bool> visited;
vector<vector<int>> result;
stack<pair<int, int>> edges;

void dfs(int node, int par) {
    visited[node] = true;
    for (auto& neighb : graph[node]) {
        if (!visited[neighb]) {
            level[neighb] = level[node] + 1;
            edges.push({node, neighb});
            dfs(neighb, node);
            low[node] = min(low[node], low[neighb]);
            if (low[neighb] >= level[node]) {
                vector<int> comp;
                while (!edges.empty()) {
                    comp.push_back(edges.top().second);
                    comp.push_back(edges.top().first);
                    edges.pop();
                    if (comp.back() == node) {
                        break;
                    }
                }
                sort(comp.begin(), comp.end());
                comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
                result.push_back(comp);
            }
        } else if (neighb != par) {
            low[node] = min(low[node], level[neighb]);
        }
    }
}

int main() {
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    graph.assign(N + 1, vector<int>());
    int from, to;
    for (int idx = 0; idx < M; idx++) {
        cin >> from >> to;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    visited.assign(N + 1, false);
    low.assign(N + 1, N);
    level.assign(N + 1, 0);
    stack<int> currEdges;
    for (int idx = 0; idx < N; idx++) {
        if (!visited[idx]) {
            dfs(idx, -1);
        }
    }
    cout << result.size() << "\n";
    for (auto& comp : result) {
        for (auto node : comp) {
            cout << node << " ";
        }
        cout << "\n";
    }
    return 0;
}