// Caminos disjuntos en aristas y en nodos, como flujo con capacidades 1.
#pragma once

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

#include "flow.h"

struct Arc {
    int from;
    int to;
};

struct Decomposition {
    std::vector<std::vector<int>> paths;
    std::vector<std::vector<int>> cycles;
    int cancelled = 0;  // aristas no dirigidas que el flujo usó en las dos direcciones
};

// Descompone un flujo entero en caminos simples de s a t y ciclos. flow_arcs tiene una entrada por cada
// unidad de flujo. Se camina por aristas sin usar: si se repite un nodo, lo recorrido desde su primera
// aparición es un ciclo y se aparta; si se llega a t, ahí hay un camino. La conservación impide atascarse.
inline Decomposition decompose_flow(int nodes, const std::vector<Arc>& flow_arcs, int s, int t) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    std::vector<std::vector<int>> out(at(nodes));
    int balance = 0;  // el valor del flujo: lo que sale de s menos lo que entra
    for (const Arc& arc : flow_arcs) {
        out[at(arc.from)].push_back(arc.to);
        if (arc.from == s) balance++;
        if (arc.to == s) balance--;
    }
    assert(balance >= 0);
    Decomposition result;
    std::vector<int> position(at(nodes), -1);

    // Camina desde start. Se detiene en stop, o si stop es -1, cuando un ciclo la devuelve a start.
    auto walk = [&](int start, int stop) {
        std::vector<int> trail = {start};
        position[at(start)] = 0;
        while (true) {
            int v = trail.back();
            if (v == stop) {
                for (int u : trail) position[at(u)] = -1;
                result.paths.push_back(trail);
                return;
            }
            assert(!out[at(v)].empty());  // lo garantiza la conservación
            int w = out[at(v)].back();
            out[at(v)].pop_back();
            if (position[at(w)] >= 0) {
                std::vector<int> cycle(trail.begin() + position[at(w)], trail.end());
                cycle.push_back(w);
                result.cycles.push_back(cycle);
                for (std::size_t k = at(position[at(w)]) + 1; k < trail.size(); k++) position[at(trail[k])] = -1;
                trail.resize(at(position[at(w)]) + 1);
                // Sin destino, se termina al volver al inicio: lo que queda en trail todavía no forma un ciclo.
                if (stop < 0 && trail.size() == 1) {
                    position[at(start)] = -1;
                    return;
                }
            } else {
                position[at(w)] = static_cast<int>(trail.size());
                trail.push_back(w);
            }
        }
    };

    for (int k = 0; k < balance; k++) walk(s, t);
    // Lo que queda está balanceado en todos los nodos: son solo ciclos.
    for (int v = 0; v < nodes; v++) {
        while (!out[at(v)].empty()) walk(v, -1);
    }
    return result;
}

// Dirigido: cada arista con capacidad 1.
inline Decomposition edge_disjoint_paths(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    MaxFlow flow(nodes);
    std::vector<int> ids;
    for (const Arc& arc : arcs) ids.push_back(flow.add_edge(arc.from, arc.to, 1));
    flow.edmonds_karp(s, t);
    std::vector<Arc> used;
    for (std::size_t k = 0; k < arcs.size(); k++) {
        if (flow.flow_on(ids[k]) == 1) used.push_back(arcs[k]);
    }
    return decompose_flow(nodes, used, s, t);
}

// No dirigido: cada arista son dos dirigidas de capacidad 1. Si el flujo usa las dos direcciones de una
// misma arista, se cancelan: siguen la conservación y el valor, y la arista queda libre.
inline Decomposition undirected_edge_disjoint_paths(int nodes, const std::vector<Arc>& edges, int s, int t) {
    MaxFlow flow(nodes);
    std::vector<std::pair<int, int>> ids;
    for (const Arc& edge : edges) {
        int forward = flow.add_edge(edge.from, edge.to, 1);
        int backward = flow.add_edge(edge.to, edge.from, 1);
        ids.emplace_back(forward, backward);
    }
    flow.edmonds_karp(s, t);
    std::vector<Arc> used;
    int cancelled = 0;
    for (std::size_t k = 0; k < edges.size(); k++) {
        long long forward = flow.flow_on(ids[k].first);
        long long backward = flow.flow_on(ids[k].second);
        if (forward == 1 && backward == 1) cancelled++;
        if (forward == 1 && backward == 0) used.push_back(edges[k]);
        if (forward == 0 && backward == 1) used.push_back({edges[k].to, edges[k].from});
    }
    Decomposition result = decompose_flow(nodes, used, s, t);
    result.cancelled = cancelled;
    return result;
}

// Corte mínimo con capacidades 1: las aristas que salen de lo alcanzable. Son las que hay que quitar.
inline std::vector<Arc> minimum_edge_cut(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    MaxFlow flow(nodes);
    for (const Arc& arc : arcs) flow.add_edge(arc.from, arc.to, 1);
    flow.edmonds_karp(s, t);
    std::vector<bool> reached = flow.reachable_from(s);
    std::vector<Arc> cut;
    for (const Arc& arc : arcs) {
        if (reached[static_cast<std::size_t>(arc.from)] && !reached[static_cast<std::size_t>(arc.to)]) cut.push_back(arc);
    }
    return cut;
}

// División de nodos. Cada nodo v distinto de s y t pasa a ser v_in = 2v y v_out = 2v + 1, unidos por
// una arista de capacidad 1. s y t no se dividen: usan un solo número, 2v + 1.
struct SplitNetwork {
    MaxFlow flow;
    std::vector<int> split_edge;  // la arista v_in → v_out de cada nodo, o -1 en s y t
    std::vector<int> arc_edge;    // la arista de la red de cada arista original
    int source;
    int sink;
};

// arc_capacity es la capacidad de las aristas originales. La de los nodos siempre es 1.
inline SplitNetwork split_network(int nodes, const std::vector<Arc>& arcs, int s, int t, long long arc_capacity) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    auto in = [&](int v) { return (v == s || v == t) ? 2 * v + 1 : 2 * v; };
    auto out = [](int v) { return 2 * v + 1; };
    SplitNetwork net{MaxFlow(2 * nodes), std::vector<int>(at(nodes), -1), {}, 2 * s + 1, 2 * t + 1};
    for (int v = 0; v < nodes; v++) {
        if (v != s && v != t) net.split_edge[at(v)] = net.flow.add_edge(in(v), out(v), 1);
    }
    for (const Arc& arc : arcs) net.arc_edge.push_back(net.flow.add_edge(out(arc.from), in(arc.to), arc_capacity));
    return net;
}

// Máximo de caminos que no comparten nodos internos. Una arista directa s → t cuenta como un camino.
inline Decomposition vertex_disjoint_paths(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    SplitNetwork net = split_network(nodes, arcs, s, t, 1);
    net.flow.edmonds_karp(net.source, net.sink);
    std::vector<Arc> used;
    for (std::size_t k = 0; k < arcs.size(); k++) {
        if (net.flow.flow_on(net.arc_edge[k]) == 1) used.push_back(arcs[k]);
    }
    return decompose_flow(nodes, used, s, t);
}

// Separador mínimo, leído del corte. Solo tiene sentido si no hay arista directa s → t.
inline std::vector<int> minimum_vertex_separator(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    long long no_limit = nodes + 1;  // ningún corte que importe paga tanto: hay uno de a lo sumo V - 2
    SplitNetwork net = split_network(nodes, arcs, s, t, no_limit);
    net.flow.edmonds_karp(net.source, net.sink);
    std::vector<bool> reached = net.flow.reachable_from(net.source);
    std::vector<int> separator;
    for (int v = 0; v < nodes; v++) {
        if (v != s && v != t && reached[static_cast<std::size_t>(2 * v)] &&
            !reached[static_cast<std::size_t>(2 * v + 1)]) {
            separator.push_back(v);
        }
    }
    return separator;
}

// ¿Se llega de s a t sin pasar por lo prohibido?
inline bool connected_without(int nodes, const std::vector<Arc>& arcs, int s, int t,
                              const std::vector<bool>& node_removed, const std::vector<bool>& arc_removed) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    std::vector<bool> seen(at(nodes), false);
    std::vector<int> pending = {s};
    seen[at(s)] = true;
    while (!pending.empty()) {
        int v = pending.back();
        pending.pop_back();
        for (std::size_t k = 0; k < arcs.size(); k++) {
            if (!arc_removed[k] && arcs[k].from == v && !seen[at(arcs[k].to)] && !node_removed[at(arcs[k].to)]) {
                seen[at(arcs[k].to)] = true;
                pending.push_back(arcs[k].to);
            }
        }
    }
    return seen[at(t)];
}