Cod sursa(job #1666624)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 28 martie 2016 10:49:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;

class dfs_class{
    const int n;
    const vector<vector<int>>& graf;
    vector<vector<int>>& comps;
    stack<int> st;
    vector<bool> viz;
    vector<int> adanc, highest_vec;
public:
    dfs_class(const vector<vector<int>>& g, vector<vector<int>>& r):
        n(g.size()), graf(g), comps(r), viz(n, false), adanc(n, 0), highest_vec(n, 0){}
    void operator()(const int cur = 0, const int prev = -1){
        viz[cur] = true;
        highest_vec[cur] = adanc[cur];
        for(const auto next : graf[cur]){
            if(next == prev){
                continue;
            }
            else if(!viz[next]){
                adanc[next] = adanc[cur] + 1;
                st.push(next);
                (*this)(next, cur);

                highest_vec[cur] = min(highest_vec[cur], highest_vec[next]);
                if(highest_vec[next] >= adanc[cur]){
                    comps.emplace_back(1, cur);
                    while(st.top() != next){
                        comps.back().push_back(st.top());
                        st.pop();
                    }
                    comps.back().push_back(st.top());
                    st.pop();
                }
            }
            else{
                highest_vec[cur] = min(highest_vec[cur], adanc[next]);
            }
        }
    }
};

int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    int n, m;
    f >> n >> m;

    vector<vector<int>> graf(n);
    for(int i = 0, a, b; i < m; ++i){
        f >> a >> b;
        --a, --b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    vector<vector<int>> comps;

    dfs_class(graf, comps)();

    g << comps.size() << '\n';
    for(const auto& x : comps){
        for(const auto y : x){
            g << y+1 << ' ';
        }
        g << '\n';
    }

    return 0;
}