Cod sursa(job #2602098)

Utilizator preda.andreiPreda Andrei preda.andrei Data 15 aprilie 2020 20:32:48
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

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

Comp ExtractComp(stack<int> &st, int last_node) {
    Comp comp{st.top()};
    do {
        st.pop();
        comp.push_back(st.top());
        st.pop();
    } while (comp.back() != last_node);
    return comp;
}

void Dfs(Graph &graph, int node, stack<int> &st, vector<Comp> &comps) {
    static auto 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);
            st.push(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> FindBiconnected(Graph &graph) {
    vector<Comp> comps;
    for (size_t i = 0; i < graph.size(); i += 1) {
        if (graph[i].time == -1) {
            stack<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 = FindBiconnected(graph);
    fout << comps.size() << "\n";

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