// Kosaraju-Sharir sobre el grafo de la clase, y lo que pasa si no se invierte.
#include <cstdio>
#include <iostream>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "digraph.h"

namespace {

std::string order_text(const std::vector<int>& order) {
    std::string text;
    for (int v : order) text += std::to_string(v) + " ";
    if (!text.empty()) text.pop_back();
    return text;
}

}  // namespace

int main() {
    Digraph g = make_digraph(8, {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 5}, {5, 3}, {6, 5}, {6, 7}, {7, 6}});
    std::cout << "Grafo: 0->1 1->2 2->0 2->3 3->4 4->5 5->3 6->5 6->7 7->6\n\n";

    std::cout << "Paso 1, DFS sobre el grafo invertido:\n";
    Digraph r = reversed(g);
    DfsTimes t = dfs_iterative(r);
    std::cout << "  nodo  inicio  fin\n";
    for (int v = 0; v < static_cast<int>(g.size()); v++) {
        std::printf("  %4d  %6d  %3d\n", v, t.start[v], t.finish[v]);
    }
    std::cout << "  terminan: " << order_text(t.finish_order) << "\n";
    std::vector<int> order(t.finish_order.rbegin(), t.finish_order.rend());
    std::cout << "  orden decreciente de fin: " << order_text(order) << "\n\n";

    std::vector<int> comp = strong_components(g);
    std::cout << "Paso 2, recorrer el original en ese orden:\n";
    std::cout << "  " << groups_text(comp) << "\n";
    std::cout << "  por la definición: " << groups_text(components_brute(g)) << "\n\n";

    std::cout << "Grafo de componentes (numeradas como salieron):\n ";
    std::set<std::pair<int, int>> between;
    for (int u = 0; u < static_cast<int>(g.size()); u++) {
        for (int v : g[u]) {
            if (comp[u] != comp[v]) between.insert({comp[u], comp[v]});
        }
    }
    for (auto [a, b] : between) std::cout << " " << a << "->" << b;
    std::cout << "\n\n";

    std::cout << "Sin invertir:\n";
    std::cout << "  orden decreciente de fin en el original: " << order_text(reverse_finish_order(g)) << "\n";
    std::vector<int> wrong = components_without_reversing(g);
    std::cout << "  " << groups_text(wrong) << "\n";
    std::cout << "  " << (same_partition(wrong, comp) ? "coincide con las componentes" : "no son las componentes") << "\n";
}