// Los problemas fáciles que están al lado de los difíciles, y fuerzas brutas para comprobarlos.
#pragma once
#include <algorithm>
#include <cstddef>
#include <numeric>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
#include "graph.h"

// 2-coloreo con BFS: cada nodo recibe el color contrario al de quien lo descubrió, y una arista entre
// dos nodos del mismo color es un ciclo impar.
inline std::optional<std::vector<int>> two_coloring(const Graph& g) {
    std::vector<int> color(g.size(), -1);
    std::queue<int> pending;
    for (std::size_t s = 0; s < g.size(); s++) {
        if (color[s] != -1) continue;
        color[s] = 0;
        pending.push(static_cast<int>(s));
        while (!pending.empty()) {
            std::size_t u = static_cast<std::size_t>(pending.front());
            pending.pop();
            for (int w : g[u]) {
                std::size_t v = static_cast<std::size_t>(w);
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    pending.push(w);
                } else if (color[v] == color[u]) {
                    return std::nullopt;
                }
            }
        }
    }
    return color;
}

// Euler: todo grado par, y todas las aristas en una sola componente. Los nodos aislados no estorban.
inline bool has_euler_cycle(const Graph& g) {
    std::vector<char> seen(g.size(), 0);
    std::size_t start = g.size();
    for (std::size_t v = 0; v < g.size(); v++) {
        if (g[v].size() % 2 != 0) return false;
        if (start == g.size() && !g[v].empty()) start = v;
    }
    if (start == g.size()) return true;
    std::vector<std::size_t> stack = {start};
    seen[start] = 1;
    while (!stack.empty()) {
        std::size_t u = stack.back();
        stack.pop_back();
        for (int w : g[u]) {
            if (!seen[static_cast<std::size_t>(w)]) {
                seen[static_cast<std::size_t>(w)] = 1;
                stack.push_back(static_cast<std::size_t>(w));
            }
        }
    }
    for (std::size_t v = 0; v < g.size(); v++) {
        if (!g[v].empty() && !seen[v]) return false;
    }
    return true;
}

// Fuerza bruta: busca un ciclo que use cada arista exactamente una vez, probando continuaciones.
inline bool euler_search(const std::vector<std::pair<int, int>>& edges, std::vector<char>& used, int at, int start, std::size_t count) {
    if (count == edges.size()) return at == start;
    for (std::size_t e = 0; e < edges.size(); e++) {
        if (used[e]) continue;
        auto [u, v] = edges[e];
        if (u != at && v != at) continue;
        used[e] = 1;
        if (euler_search(edges, used, u == at ? v : u, start, count + 1)) {
            used[e] = 0;
            return true;
        }
        used[e] = 0;
    }
    return false;
}

inline bool euler_cycle_brute(const Graph& g) {
    std::vector<std::pair<int, int>> edges = edge_list(g);
    if (edges.empty()) return true;
    std::vector<char> used(edges.size(), 0);
    return euler_search(edges, used, edges[0].first, edges[0].first, 0);
}

// Hay camino hamiltoniano si el camino simple más largo tiene V − 1 aristas. Fuerza bruta, grafo no dirigido.
inline int longest_from(const Graph& g, std::size_t u, std::vector<char>& used) {
    int best = 0;
    used[u] = 1;
    for (int w : g[u]) {
        if (!used[static_cast<std::size_t>(w)]) best = std::max(best, 1 + longest_from(g, static_cast<std::size_t>(w), used));
    }
    used[u] = 0;
    return best;
}

inline int longest_simple_path(const Graph& g) {
    int best = 0;
    std::vector<char> used(g.size(), 0);
    for (std::size_t s = 0; s < g.size(); s++) best = std::max(best, longest_from(g, s, used));
    return best;
}

// Grafos dirigidos para el camino más largo en un DAG, medido en aristas.
using Dag = std::vector<std::vector<int>>;

// L[u] es el mayor número de aristas de un camino que sale de u. Los sucesores se calculan primero.
inline int longest_path_dag(const Dag& g) {
    std::vector<int> pending(g.size(), 0);
    Dag inverse(g.size());
    for (std::size_t u = 0; u < g.size(); u++) {
        pending[u] = static_cast<int>(g[u].size());
        for (int v : g[u]) inverse[static_cast<std::size_t>(v)].push_back(static_cast<int>(u));
    }
    std::vector<int> ready;
    for (std::size_t u = 0; u < g.size(); u++) {
        if (pending[u] == 0) ready.push_back(static_cast<int>(u));
    }
    std::vector<int> length(g.size(), 0);
    int best = 0;
    while (!ready.empty()) {
        std::size_t u = static_cast<std::size_t>(ready.back());
        ready.pop_back();
        best = std::max(best, length[u]);
        for (int w : inverse[u]) {
            std::size_t p = static_cast<std::size_t>(w);
            length[p] = std::max(length[p], length[u] + 1);
            if (--pending[p] == 0) ready.push_back(w);
        }
    }
    return best;
}

inline int longest_directed_from(const Dag& g, std::size_t u) {
    int best = 0;
    for (int v : g[u]) best = std::max(best, 1 + longest_directed_from(g, static_cast<std::size_t>(v)));
    return best;
}

inline int longest_path_dag_brute(const Dag& g) {
    int best = 0;
    for (std::size_t u = 0; u < g.size(); u++) best = std::max(best, longest_directed_from(g, u));
    return best;
}