Cod sursa(job #3233949)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 5 iunie 2024 15:37:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 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<size_t> low_link;
    stack<size_t> st;
    vector<bool> done;
    vector<set<size_t>> ctc = vector<set<size_t>>();
    size_t time = 0;

    void dfs(size_t node, size_t src_time) {
        st.push(node);
        start[node] = ++time;
        low_link[node] = time;

        for (auto neigh : adj[node]) {
            if (done[neigh] && start[neigh] < src_time)
                continue;

            if (start[neigh] == 0) {
                dfs(neigh, src_time);
            }

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

        done[node] = true;

        if (low_link[node] == start[node]) {
            ctc.push_back(set<size_t>());
            while (true) {
                ctc.back().insert(st.top());
                if (!(st.top() == node)) {
                    st.pop();
                } else {
                    st.pop();
                    break;
                }
            }
        }
    }

 public:
    explicit Solutuion(ifstream &in) {
        in >> N >> M;
        adj.resize(N + 1);
        start.resize(N + 1, 0);
        low_link.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() {
        for (size_t node = 1; node <= N; node++)
            if (start[node] == 0)
                dfs(node, time + 1);

        return ctc;
    }
};

int main() {
    ifstream in("ctc.in");
    ofstream out("ctc.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;
}