Cod sursa(job #2596153)

Utilizator zhm248Mustatea Radu zhm248 Data 9 aprilie 2020 12:46:38
Problema Componente biconexe Scor 54
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>
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];

    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(vector<vector<int>>& sol, vector<int>& idx, vector<int>& low,
        int& index, int node, int parent, stack<pair<int, int>>& edges) {
        idx[node] = index;
        low[node] = index;
        index++;
        for (int i = 0; i < (int)adj[node].size(); ++i) {
            if (!idx[adj[node][i]]) {
                edges.push(pair<int, int>(node, adj[node][i]));
                dfs(sol, idx, low, index, adj[node][i], node, edges);
                low[node] = min(low[node], low[adj[node][i]]);
                if (low[adj[node][i]] >= idx[node]) {
                    vector<int> new_solution;
                    int x, y;
                    new_solution.emplace_back(edges.top().second);
                    do {
                        x = edges.top().first;
                        y = edges.top().second;
                        new_solution.emplace_back(x);
                        edges.pop();
                    } while (x != node || y != adj[node][i]);
                    sol.emplace_back(new_solution);
                }
            } else {
                if (parent != adj[node][i]) {
                    low[node] = min(low[node], idx[adj[node][i]]);
                }
            }
        }
    }

    vector<vector<int>> get_result() {
        vector<int> idx(n + 1, 0);
        vector<int> low(n + 1, 0);
        int index = 1;
        vector<vector<int>> sol;
        stack<pair<int, int>> edges;
        for (int i = 1; i <= n; ++i) {
            if (!idx[i]) {
                dfs(sol, idx, low, index, i, 0, edges);
            }
        }
        return sol;
    }

    void print_output(vector<vector<int>> result) {
        ofstream fout("biconex.out");
        fout << result.size() << '\n';
        for (int i = 0; i < (int)result.size(); ++i) {
            for (int j = 0; j < (int)result[i].size(); ++j) {
                fout << result[i][j] << ' ';
            }
            fout << '\n';
        }
        fout.close();
    }
};

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