// Las calles de un mapa llegan una a una, al azar, y tras cada una se pregunta si dos nodos al
// azar están conectados. Cuenta el trabajo de DFS y de union-find. No mide tiempos.
#include <cstdint>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

#include "counting_forest.h"
#include "map_file.h"
#include "traversals.h"

namespace {

// DFS desde a hasta encontrar b. Suma los nodos marcados y las entradas leídas.
bool connected_by_dfs(const Graph& graph, int a, int b, std::vector<int>& stamp, int query, std::int64_t& reads) {
    std::vector<int> stack{a};
    stamp[a] = query;
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        if (u == b) {
            return true;
        }
        for (const Edge& edge : graph.neighbors(u)) {
            reads++;
            if (stamp[edge.to] != query) {
                stamp[edge.to] = query;
                stack.push_back(edge.to);
            }
        }
    }
    return false;
}

}  // namespace

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "uso: online_connectivity mapa\n";
        return 1;
    }
    int n = 0;
    std::vector<MapEdge> edges = read_map_edges(argv[1], n);
    std::mt19937 rng(14);
    for (std::size_t i = edges.size() - 1; i > 0; i--) {
        std::swap(edges[i], edges[rng() % (i + 1)]);
    }

    Graph graph(n);
    CountingForest forest(n, true, true);
    std::vector<int> stamp(n, -1);
    std::int64_t dfs_reads = 0;
    std::int64_t answers_yes = 0;
    std::size_t joined_at = 0;
    int query = 0;
    for (const MapEdge& edge : edges) {
        graph.add_edge(edge.u, edge.v, edge.meters);
        forest.unite(edge.u, edge.v);
        int a = static_cast<int>(rng() % n);
        int b = static_cast<int>(rng() % n);
        bool by_dfs = connected_by_dfs(graph, a, b, stamp, query, dfs_reads);
        bool by_forest = forest.find(a) == forest.find(b);
        if (by_dfs != by_forest) {
            std::cout << "no coinciden\n";
            return 1;
        }
        answers_yes += by_dfs ? 1 : 0;
        query++;
        if (joined_at == 0 && forest.sets() == 1) {
            joined_at = static_cast<std::size_t>(query);
        }
    }
    std::cout << "nodos: " << n << ", aristas que llegan: " << edges.size() << ", preguntas: " << query << "\n";
    std::cout << "respuestas si: " << answers_yes << " (todo unido tras la arista " << joined_at << ")\n";
    std::cout << "DFS en cada pregunta, entradas leidas: " << dfs_reads << "\n";
    std::cout << "union-find, saltos por parent: " << forest.hops() << "\n";
    std::cout << "por pregunta: DFS " << static_cast<double>(dfs_reads) / query << ", union-find "
              << static_cast<double>(forest.hops()) / query << "\n";

    // Si primero llegan todas las aristas, basta una pasada y un arreglo.
    std::vector<int> labels = component_labels(graph);
    std::cout << "todas primero: una pasada lee " << 2 * edges.size() << " entradas, y cada pregunta compara "
              << "dos etiquetas: " << (labels[0] == labels[n - 1] ? "conectados" : "separados") << "\n";
    return 0;
}