Cod sursa(job #1896254)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 februarie 2017 16:17:08
Problema Componente biconexe Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

struct Node
{
    int time;
    int lowpoint;
    bool in_stack;
    vector<int> edges;
};

using Graph = vector<Node>;

void Dfs(Graph &g, int node, stack<int> &st, vector<vector<int>> &comps, int father = -1)
{
    static int time = 0;
    g[node].time = g[node].lowpoint = ++time;
    st.push(node);
    g[node].in_stack = true;

    for (int next : g[node].edges) {
        if (next == father) {
            continue;
        }

        if (g[next].time == 0) {
            Dfs(g, next, st, comps, node);
        }

        if (g[next].in_stack && g[next].lowpoint >= g[node].time) {
            vector<int> new_comp;
            while (st.top() != node) {
                new_comp.push_back(st.top());
                g[st.top()].in_stack = false;
                st.pop();
            }
            new_comp.push_back(node);
            comps.push_back(new_comp);
        }

        if (g[next].in_stack) {
            g[node].lowpoint = min(g[node].lowpoint, g[next].lowpoint);
        } else {
            g[node].lowpoint = min(g[node].lowpoint, g[next].time);
        }
    }
}

vector<vector<int>> FindComponents(Graph &g)
{
    for (auto &node : g) {
        node.time = node.lowpoint = 0;
        node.in_stack = false;
    }

    vector<vector<int>> components;
    for (unsigned i = 0; i < g.size(); ++i) {
        if (g[i].time == 0) {
            stack<int> st;
            Dfs(g, i, st, components);
        }
    }
    return components;

}

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

    int n, m;
    fin >> n >> m;

    Graph graph(n);
    while (m--) {
        int x, y;
        fin >> x >> y;
        graph[x - 1].edges.push_back(y - 1);
        graph[y - 1].edges.push_back(x - 1);
    }

    auto components = FindComponents(graph);
    fout << components.size() << "\n";

    for (const auto &comp : components) {
        for (int node : comp) {
            fout << node + 1 << " ";
        }
        fout << "\n";
    }

    return 0;
}