Cod sursa(job #2462872)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 septembrie 2019 22:37:41
Problema Componente biconexe Scor 54
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

using Graph = vector<Node>;
using Edge = pair<int, int>;

vector<int> ExtractComp(Graph &g, stack<Edge> &st, int last_node)
{
    vector<int> 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 &g, int node, stack<Edge> &st, vector<vector<int>> &comps)
{
    static int time = 0;
    g[node].low = g[node].time = (time += 1);

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

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

vector<vector<int>> FindComps(Graph &g)
{
    vector<vector<int>> comps;
    for (size_t i = 0; i < g.size(); i += 1) {
        if (g[i].time == -1) {
            stack<Edge> st;
            Dfs(g, 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 = FindComps(graph);
    fout << comps.size() << "\n";

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