Cod sursa(job #3233973)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 5 iunie 2024 17:12:50
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.22 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Solutuion {
 private:
    unsigned long long N;
    unsigned long long M;
    vector<vector<unsigned long long>> adj;
    vector<unsigned long long> start;
    vector<unsigned long long> parent;
    vector<unsigned long long> low_link;
    vector<set<unsigned long long>> bicon;
    stack<pair<unsigned long long, unsigned long long>> st;
    unsigned long long time;

    void dfs(unsigned long long node) {
        start[node] = ++time;
        low_link[node] = time;

        for (auto neigh : adj[node]) {
            if (neigh == parent[node])
                continue;

            if (start[neigh] == 0) {
                st.push({node, neigh});
                parent[neigh] = node;
                dfs(neigh);

                if (low_link[neigh] >= start[node]) {
                    bicon.push_back(set<unsigned long long>());
                    while (true) {
                        auto top = st.top();
                        bicon.back().insert(top.first);
                        bicon.back().insert(top.second);

                        if (top.first != node) {
                            st.pop();
                        } else {
                            st.pop();
                            break;
                        }
                    }
                }
            }

            low_link[node] = min(low_link[node], low_link[neigh]);
        }
    }

    void dfs_root(unsigned long long root) {
        start[root] = ++time;
        low_link[root] = time;

        for (auto neigh : adj[root]) {
            if (start[neigh] == 0) {
                st.push({root, neigh});
                parent[neigh] = root;
                dfs(neigh);

                bicon.push_back(set<unsigned long long>());
                while (true) {
                    auto top = st.top();
                    bicon.back().insert(top.first);
                    bicon.back().insert(top.second);
                    if (top.first != root) {
                        st.pop();
                    } else {
                        st.pop();
                        break;
                    }
                }
            }
        }

        st.pop();
    }

 public:
    explicit Solutuion(ifstream &in) {
        in >> N >> M;
        adj.resize(N + 1);
        start.resize(N + 1, 0);
        parent.resize(N + 1, 0);
        low_link.resize(N + 1, 0);

        unsigned long long node1, node2;
        for (unsigned long long i = 1; i <= M; i++) {
            in >> node1 >> node2;

            adj[node1].push_back(node2);
            adj[node2].push_back(node1);
        }
    }

    vector<set<unsigned long long>> solve() {
        for (unsigned long long node = 1; node <= N; node++)
            if (start[node] == 0) {
                time = 0;
                dfs_root(node);
            }
        
        return bicon;
    }
};

int main() {
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    
    auto solution = Solutuion(in).solve();

    out << solution.size() << endl;
    for (auto sol : solution) {
        copy(sol.begin(), sol.end(), ostream_iterator<unsigned long long>(out, " "));
        out << endl;
    }
    
    in.close();
    out.close();
    return 0;
}