Cod sursa(job #3225949)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 19 aprilie 2024 13:59:54
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.12 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Solutuion {
 private:
    size_t N;
    size_t M;
    vector<vector<size_t>> adj;
    vector<size_t> start;
    vector<set<size_t>> biconex;
    vector<size_t> parents;
    stack<size_t> s;
    size_t time = 0;

    size_t dfs(size_t root, size_t node) {
        start[node] = ++time;
        s.push(node);

        size_t min_node = node;

        bool has_2_children = false;
        
        for (auto neigh : adj[node]) {
            if (neigh == parents[node])
                continue;

            if (start[neigh] == 0) {
                parents[neigh] = node;
                size_t rez = dfs(root, neigh);

                if (!has_2_children) {
                    for (auto neigh : adj[node]) {
                        if (start[neigh] == 0) {
                            has_2_children = true;
                            break;
                        }
                    }
                }
                
                if ((start[rez] >= start[node] && node != root) ||
                    (node == root && has_2_children)) {
                    while (s.top() != neigh) {
                        biconex.back().insert(s.top());
                        s.pop();
                    }
                    biconex.back().insert(neigh);
                    s.pop();
                    
                    biconex.back().insert(node);
                    biconex.push_back(set<size_t>());
                    continue;
                }
                
                if (start[node] > start[rez]) {
                    if (start[min_node] > start[rez])
                        min_node = rez;
                }
                
            } else if (start[node] > start[neigh]) {
                if (start[min_node] > start[neigh])
                    min_node = neigh;
            }
        }

        if (node == root)
            biconex.pop_back();
        return min_node;
    }

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

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

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

    vector<set<size_t>> solve() {
        bool end = false;
        size_t source;

        while (!end) {
            end = true;
            for (size_t node = 1; node <= N; node++)
                if (start[node] == 0) {
                    source = node;
                    end = false;
                    biconex.push_back(set<size_t>());

                    dfs(source, source);
                    break;
                }
        }

        return biconex;
    }
};

int main() {
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    
    vector<set<size_t>> solution = Solutuion(in).solve();

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