Cod sursa(job #3357891)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 19:32:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <vector>
#include <fstream>
#include <stack>
#include <algorithm>

std::vector<std::vector<int>> graph;
std::vector<int> time_of_entry;
std::vector<int> low;
std::vector<bool> visited;
std::stack<std::pair<int, int>> edge_stack;
std::vector<std::vector<int>> components;
int timer = 0;

void dfs(int node, int parent = -1) {
    visited[node] = true;
    time_of_entry[node] = low[node] = ++timer;
    int children = 0;

    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;

        if (visited[neighbor]) {
            if (time_of_entry[neighbor] < time_of_entry[node]) {
                edge_stack.push({node, neighbor});
                low[node] = std::min(low[node], time_of_entry[neighbor]);
            }
        } else {
            edge_stack.push({node, neighbor});
            dfs(neighbor, node);
            children++;
            low[node] = std::min(low[node], low[neighbor]);

            if (low[neighbor] >= time_of_entry[node]) {
                std::vector<int> component;
                while (true) {
                    auto [u, v] = edge_stack.top();
                    edge_stack.pop();
                    component.push_back(u);
                    component.push_back(v);
                    if ((u == node && v == neighbor) || (u == neighbor && v == node)) break;
                }
                std::sort(component.begin(), component.end());
                component.erase(std::unique(component.begin(), component.end()), component.end());
                components.push_back(component);
            }
        }
    }
}

int main() {
    std::ifstream input("biconex.in");
    std::ofstream output("biconex.out");

    int n, m;
    input >> n >> m;

    graph.resize(n + 1);
    time_of_entry.assign(n + 1, 0);
    low.assign(n + 1, 0);
    visited.assign(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int x, y;
        input >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    output << components.size() << '\n';
    for (const auto& component : components) {
        for (int node : component) {
            output << node << ' ';
        }
        output << '\n';
    }

    return 0;
}