Cod sursa(job #3225593)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 18 aprilie 2024 02:33:01
Problema Componente biconexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.65 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<bool> done;
    vector<set<size_t>> biconex = vector<set<size_t>>(1, set<size_t>());
    size_t time = 0;

    size_t dfs(size_t root, size_t node) {
        size_t min_node = 0;

        start[node] = ++time;
        
        for (auto neigh : adj[node]) {
            if (start[neigh] == 0) {
                size_t rez = dfs(root, neigh);
                
                if (rez == node || rez == 0) {
                    biconex.back().insert(node);
                    biconex.push_back(set<size_t>());
                    continue;
                }
                
                if (start[node] > start[rez]) {
                    if (min_node == 0) {
                        min_node = rez;
                        continue;
                    }

                    if (start[min_node] > start[rez])
                        min_node = rez;
                }
                
            } else if (start[node] > start[neigh]) {
                if (min_node == 0) {
                    min_node = neigh;
                    continue;
                }

                if (start[min_node] > start[neigh])
                    min_node = neigh;
            }
        }

        if (node != root || (node == root && biconex.front().size() == 0))
            biconex.back().insert(node);
        return min_node;
    }

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

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

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

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

        while (!done) {
            done = true;
            for (size_t node = 1; node <= N; node++)
                if (start[node] == 0) {
                    source = node;
                    done = false;

                    dfs(source, source);
                    break;
                }
        }

        if (biconex.back().size() == 0)
            biconex.pop_back();
        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;
}