Cod sursa(job #2406468)

Utilizator Marose1928Marius Tudosoiu Marose1928 Data 15 aprilie 2019 19:26:19
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <fstream>
#include <vector>
#include <algorithm>
#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];

    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();
    }

    vector<vector<int>> get_result() {
        /*
        TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
        de adiacenta in adj.
        */
        vector<vector<int>> sol;
        vector<int> idx(n + 1, -1);
        vector<int> low(n + 1);
        // vector<vector<int>> children(n + 1);
        stack<int> stack;
        int time = 0;
        for (int i = 1;  i <= n; ++i) {
            if (idx[i] == -1) {
                dfs(i, time, idx, low, sol, stack);
            }
        }
        return sol;
    }

    void dfs(int source, int time, vector<int> &idx, vector<int> &low,
             vector<vector<int>> &sol, stack<int> &stack) {

        stack.push(source);

        idx[source] = time;
        low[source] = time;
        time++;
        for (int x : adj[source]) {
            if (idx[x] == -1) {
                // children[source].push_back(x);
                dfs(x, time, idx, low, sol, stack);
                low[source] = min(low[source], low[x]);

                if (low[x] >= idx[source]) {
                    vector<int> CB;
                    CB.push_back(source);
                    while (stack.top() != x) {
                        CB.push_back(stack.top());
                        stack.pop();
                    }
                    CB.push_back(stack.top());
                    stack.pop();
                    sol.push_back(CB);
                }
            } else {
                low[source] = min(low[source], idx[x]);
            }
        }
    }

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

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