Cod sursa(job #2753457)

Utilizator preda.andreiPreda Andrei preda.andrei Data 22 mai 2021 22:44:48
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

struct Node {
    vector<int> edges;
    int time = -1;
    int low = -1;
    bool in_stack = false;
};

using Graph = vector<Node>;
using Comp = vector<int>;

Comp ExtractComp(stack<pair<int, int>>& st, int last_node) {
    Comp comp;
    comp.push_back(st.top().second);

    while (comp.back() != last_node) {
        comp.push_back(st.top().first);
        st.pop();
    }
    return comp;
}

void Dfs(Graph& graph, int node, stack<pair<int, int>>& st, vector<Comp>& comps) {
    static int time = 0;
    graph[node].time = graph[node].low = (time += 1);

    for (const auto& next : graph[node].edges) {
        if (graph[next].time == -1) {
            st.push({node, next});
            Dfs(graph, next, st, comps);
            graph[node].low = min(graph[node].low, graph[next].low);

            if (graph[next].low >= graph[node].time) {
                comps.push_back(ExtractComp(st, node));
            }
        }
        graph[node].low = min(graph[node].low, graph[next].time);
    }
}

vector<Comp> Comps(Graph& graph) {
    vector<Comp> comps;
    for (size_t i = 0; i < graph.size(); i += 1) {
        if (graph[i].time == -1) {
            stack<pair<int, int>> st;
            Dfs(graph, i, st, comps);
        }
    }
    return comps;
}

int main() {
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    int nodes, edges;
    fin >> nodes >> edges;

    Graph graph(nodes);
    for (int i = 0; i < edges; i += 1) {
        int a, b;
        fin >> a >> b;
        graph[a - 1].edges.push_back(b - 1);
        graph[b - 1].edges.push_back(a - 1);
    }

    auto comps = Comps(graph);
    fout << comps.size() << "\n";

    for (const auto& comp : comps) {
        for (const auto& node : comp) {
            fout << node + 1 << " ";
        }
        fout << "\n";
    }
    return 0;
}