Cod sursa(job #2928663)

Utilizator sincasilviuSinca Silviu-Gabriel sincasilviu Data 23 octombrie 2022 17:05:53
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Tarjan {
private:
    int N, M, id, ctc_count;
    vector<vector<int>> adj_list;
    vector<int> ids;
    vector<int> low;
    vector<bool> sel;
    stack<int> st;
    vector<int> ctc;
    unordered_map<int, vector<int>> componente;

public:
    Tarjan(int N, int M, vector<vector<int>> adj_list) {
        this->N = N;
        this->M = M;
        this->adj_list = std::move(adj_list);
        this->ids.resize(N+1, -1);
        this->low.resize(N+1, 0);
        this->sel.resize(N+1, false);
        this->ctc.resize(N+1);
        this->id = 0;
        this->ctc_count = 0;
        componente.reserve(N+1);
    }

    void dfs(int node) {
        st.push(node);
        sel[node] = true;
        ids[node] = id;
        low[node] = id++;

        for (auto neighbour : adj_list[node]) {
            if (ids[neighbour] == -1)
                dfs(neighbour);
            if (sel[neighbour])
                low[node] = min(low[node], low[neighbour]);
        }

        if (ids[node] == low[node]) {
            while(!st.empty()) {
                int el = st.top();
                sel[el] = false;
                ctc[el] = ctc_count;
                componente[ctc_count].push_back(el);
                st.pop();
                if (el == node)
                    break;
            }
            ctc_count++;
        }
    }

    unordered_map<int, vector<int>> findCtc() {
        for (int i = 1; i <= N; i++) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
        return componente;
    }

    int get_ctc_count() const {
        return this->ctc_count;
    }
};

int main() {
    ifstream fin("ctc.in");
    fstream fout("ctc.out");

    int n, m, a, b;
    fin >> n >> m;

    vector<vector<int>> lista_ad(n + 1);

    for (int i = 1; i <= m; i++) {
        fin >> a >> b;
        lista_ad[a].push_back(b);
    }

    Tarjan tarjan(n, m, lista_ad);
    unordered_map<int, vector<int>> ctc = tarjan.findCtc();
    int count = tarjan.get_ctc_count();

    fout << count << '\n';

    for (const auto& componenta : ctc) {
        vector<int> aux = componenta.second;
        std::sort(aux.begin(), aux.end());
        for (auto nod : aux)
            fout << nod << ' ';
        fout << endl;
    }

    return 0;
}