Cod sursa(job #3148989)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 5 septembrie 2023 17:19:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <vector>
#include <fstream>
#include <stack>
#include <unordered_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<std::pair<int, int>> stack;

std::vector<std::unordered_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 root = 0) {

    time_of_entry[node] = low[node] = timer++;
    visited[node] = true;
    int children = 0;
    for (const auto &x: graph[node]) {
        if (x == root) continue;
        if (visited[x]) {
            low[node] = std::min(low[node], time_of_entry[x]);
        } else {
            stack.emplace(x, node);
            dfs(x, node);
            low[node] = std::min(low[node], low[x]);
            if (low[x] >= time_of_entry[node]) {
                components.emplace_back();
                while (!stack.empty()) {
                    auto top = stack.top();
                    stack.pop();

                    components.back().insert(top.first);
                    components.back().insert(top.second);
                    if (top.first == x && top.second == node) break;
                }
            }
            children++;
        }
    }
}

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

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

    while (m--) {
        int x, y;
        input >> x >> y;
        graph.add_edge(x, y);
    }

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

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

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

    return 0;
}