Cod sursa(job #3225943)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 19 aprilie 2024 13:33:52
Problema Componente biconexe Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.71 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<set<size_t>>();
    size_t time = 0;

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

        size_t min_node = node;

        bool has_2_children = false;
        
        for (auto neigh : adj[node]) {
            if (start[neigh] == 0) {
                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) || has_2_children) {
                    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();
        } else {
            biconex.back().insert(node);
        }
        return min_node;
    }

 public:
    explicit Solutuion(ifstream &in) {
        in >> N >> M;
        adj.resize(N + 1);
        start.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;
}