Cod sursa(job #2402693)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 10 aprilie 2019 22:05:16
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stack>
#include <vector>
#include <fstream>

using std::stack;
using std::vector;

std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");

class Graph {
  private:
    int n;
    vector<vector<int>> ad;

    stack<int> st;
    vector<int> lvl, low;
    vector<vector<int>> bcc;

    static inline int min(int x, int y) {
        return x < y ? x : y;
    }

    void dfs(int node, int depth) {
        low[node] = lvl[node] = depth;
        for (int nghb : ad[node])
            if (!lvl[nghb]) {
                st.push(nghb);
                dfs(nghb, depth + 1);
                low[node] = min(low[node], low[nghb]);

                if (low[nghb] >= lvl[node]) {
                    bcc.push_back(vector<int>(1, node));
                    while (st.top() != nghb) {
                        bcc.back().push_back(st.top());
                        st.pop();
                    }
                    bcc.back().push_back(st.top());
                    st.pop();
                }
            }
            else if (lvl[nghb] < lvl[node] - 1)
                low[node] = min(low[node], low[nghb]);
    }

  public:
    Graph(int n) {
        this->n = n;
        ad.resize(n + 1);
    }

    void addEdge(int x, int y) {
        ad[x].push_back(y);
        ad[y].push_back(x);
    }

    void biconnectivity() {
        lvl.resize(n + 1);
        low.resize(n + 1);

        bcc.reserve(n);
        dfs(1, 1);

        fout << bcc.size() << '\n';
        for (vector<int> comp : bcc) {
            for (int node : comp)
                fout << node << ' ';
            fout << '\n';
        }
    }
};

int main() {
    int n, m;
    fin >> n >> m;
    
    Graph graph(n);
    for (int i = 0; i < m; i++) {
        int x, y; fin >> x >> y;
        graph.addEdge(x, y);
    }

    graph.biconnectivity();
    fout.close();
    return 0;
}