Cod sursa(job #3357789)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 14:54:13
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <vector>
#include <fstream>
#include <stack>
#include <set>

#define MAX_SIZE 100001

std::vector<int> time_of_entry(MAX_SIZE, 0);
std::vector<bool> visited(MAX_SIZE, false);
std::vector<int> low(MAX_SIZE, 0);
std::stack<int> stack;

std::vector<std::set<int>> components;
int timer = 0;

struct Graph {
private:
    std::vector<std::vector<int>> vec;

public:
    explicit Graph(int nodes) {
        vec.resize(nodes + 1);
    }

    void add_edge(int to, int from) {
        vec[to].push_back(from);
        vec[from].push_back(to);
    }

    const std::vector<int> &operator[](int node) {
        return vec[node];
    }
};

Graph graph(MAX_SIZE);

void dfs(int node, int parent) {
    time_of_entry[node] = low[node] = timer++;
    visited[node] = true;
    stack.push(node);

    for (const auto &neighbor : graph[node]) {
        if (neighbor == parent) continue;
        if (visited[neighbor]) {
            low[node] = std::min(low[node], time_of_entry[neighbor]);
        } else {
            dfs(neighbor, node);
            low[node] = std::min(low[node], low[neighbor]);
        }
    }

    if (low[node] == time_of_entry[node]) {
        std::set<int> component;
        while (!stack.empty()) {
            int current = stack.top();
            stack.pop();
            component.insert(current);
            if (current == node) break;
        }
        components.push_back(component);
    }
}

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

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

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

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

    output << components.size() << '\n';

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

    return 0;
}