Cod sursa(job #2198253)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 23 aprilie 2018 23:44:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
#include <bits/stdc++.h>
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];
    vector<int> idx;
    vector<int> low;
    vector<int> parent;
    int time = 0;
 
    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 dump(int v, stack<int> &s, vector<int> &bcc) {
        int u;
        do {
            u = s.top();
            s.pop();
            bcc.push_back(u);
        } while (u != v);
    }
 
    void dfsBCC(int v, stack<int> &s, vector<vector<int>> &bccs) {
        time++;
        idx[v] = time;
        low[v] = time;
        s.push(v);
        int nkids = 0;
        bool cv = false;
 
        for (int u : adj[v]) 
            if (!idx[u]) {
                nkids++;
                // if (!parent[v]) {
                //     vector<int> bcc;
                //     dump(v, s, bcc);
                //     bccs.push_back(bcc);
                //     s.push(v);
                // }
                // s.push()
                parent[u] = v;
                dfsBCC(u, s, bccs);
                low[v] = min(low[v], low[u]);
                if (low[u] >= idx[v] && parent[v] || !parent[v]) {
                    vector<int> bcc;
                    bcc.push_back(v);
                    dump(u, s, bcc);
                    bccs.push_back(bcc);
                }
            }
            else if (u != parent[v])
                low[v] = min(low[v], idx[u]);
 
        // if (!parent[v]) {
        //     vector<int> bcc;
        //     dump(v, s, bcc);
        //     bccs.push_back(bcc);
        // }
    }
 
    vector<vector<int>> get_result() {
        /*
        TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
        de adiacenta in adj.
        */
        vector<vector<int>> sol;
        stack<int> s;
        idx.resize(n + 1, 0);
        low.resize(n + 1);
        parent.resize(n + 1, 0);
 
        for (int i = 1; i <= n; i++)
            if (!idx[i])
                dfsBCC(i, s, sol);
     
        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;
}