Cod sursa(job #2605818)

Utilizator ana_maria.milcuAna-Maria Milcu ana_maria.milcu Data 25 aprilie 2020 21:20:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

const int kNmax = 100005;

class Task {
public:
    void solve() {
        read_input();
        print_output(get_result());
    }

private:
    int n;
    int m;
    vector<int> adj[kNmax];

    struct Edge {
        Edge(int x_, int y_) {
            x = x_;
            y = y_;
        }
        int x;
        int y;
    };

    void read_input() {
        ifstream fin("biconex.in");
        fin >> n >> m;
        for (int i = 1, x, y; i <= m; i++) {
            fin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        fin.close();
    }

    void dfs(int u, int parent, vector<vector<int>> &sol, stack<int> &s,
             vector<int> &disc, vector<int> &low, int &index) {
        disc[u] = low[u] = index;
        index++;
        int x;
        s.push(u);
        for (int v : adj[u]) {
            if (v == parent)
                continue;
            if (!disc[v]) {
                dfs(v, u, sol, s, disc, low, index);
                low[u] = min(low[u], low[v]);
                if (low[v] >= disc[u]) {
                    vector<int> component;
                    while (x != v) {
                        x = s.top();
                        s.pop();
                        component.push_back(x);
                    }
                    component.push_back(u);
                    sol.push_back(component);
                }
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

    vector<vector<int>> get_result() {
        /*
        TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
        de adiacenta in adj.
        */
        int index = 0;
        vector<vector<int>> sol;
        vector<int> disc(n + 1, 0);
        vector<int> low(n + 1, INT32_MAX);
        stack<int> s;
        dfs(1, -1, sol, s, disc, low, index);
        return sol;
    }

    void print_output(vector<vector<int>> result) {
        ofstream fout("biconex.out");
        fout << result.size() << '\n';
        for (const auto& ctc : result) {
            for (int nod : ctc) {
                fout << nod << ' ';
            }
            fout << '\n';
        }
        fout.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}