Cod sursa(job #1970921)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 19 aprilie 2017 18:20:19
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include <vector>
#include <stack>
#include <fstream>
#include <iostream>

using namespace std;

class BCC {
    int n;
    vector<vector<int>> G, bcs;
    vector<bool> isAncestor;
    vector<int> depth, lowlink, wh;
    stack<int> st;
    
    void dfs(int x, int f) {
        depth[x] = depth[f] + 1;
        lowlink[x] = depth[x];
        st.push(x);
        isAncestor[x] = true;
        
        for (auto y : G[x]) {
            if (y == f)
                continue;

            if (!depth[y]) {
                // DFS edge.
                dfs(y, x);
                lowlink[x] = min(lowlink[x], lowlink[y]);

                // x is critical node.
                if (lowlink[y] >= depth[x]) {
                    vector<int> bc;
                    while (st.top() != x) {
                        wh[st.top()] = bcs.size();
                        bc.push_back(st.top());
                        st.pop();
                    }
                    bc.push_back(x);
                    bcs.push_back(bc);
                }

                // Critical Edge.
                if (lowlink[y] > depth[x]) {

                }
            } else if (isAncestor[y]) {
                // Back edge.
                lowlink[x] = min(lowlink[x], depth[y]);
            } else {
                // Forward edge.
            }
        }
        
        isAncestor[x] = false;
    }
    
  public:
  
    BCC(vector<vector<int>>& G) : G(G) {
        n = G.size() - 1;
        
        depth = lowlink = wh = vector<int>(n+1);
        isAncestor = vector<bool>(n+1);

        for (int i = 1; i <= n; ++i) {
            if (!depth[i]) {
                dfs(i, 0);
            }
        }
    }

    vector<vector<int>> getBcs() {
        return bcs;
    }
};

int main() {
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n, m;

    cin >> n >> m;

    vector<vector<int>> G(n+1);

    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // cerr << "Here" << endl;
    BCC bcc(G);

    auto bcs = bcc.getBcs();

    cout << bcs.size() << "\n";
    for (auto& bc : bcs) {
        for (auto el : bc) {
            cout << el << " ";
        }
        cout << "\n";
    }
}