#include "Graph.h"
#include "DSU.h"
#include <stack>
#include <algorithm>
#include <climits>

static bool reachableWithoutEdge(const std::vector<std::set<std::pair<int, int>>>& g,
                                 int from, int to, int a, int b, int w) {
    std::vector<char> visited(g.size(), 0);
    std::stack<int> st;
    st.push(from);
    visited[from] = 1;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        for (auto& e : g[u]) {
            int v = e.first, ew = e.second;
            if (u == a && v == b && ew == w) continue;
            if (u == b && v == a && ew == w) continue;
            if (!visited[v]) {
                visited[v] = 1;
                st.push(v);
            }
        }
    }
    return visited[to] != 0;
}

static bool isBridge(const std::vector<std::set<std::pair<int, int>>>& g, int a, int b, int w) {
    return !reachableWithoutEdge(g, a, b, a, b, w);
}

int Graph::checkEuler(bool& circleExist) const {
    circleExist = false;
    if (directed) return 0;
    if (n == 0) return 0;

    auto g = toAdjList();
    std::vector<int> deg(n + 1, 0);
    DSU dsu(n);
    for (int u = 1; u <= n; ++u)
        for (auto& e : g[u]) {
            ++deg[u];
            dsu.unite(u, e.first);
        }

    int start = 0;
    for (int u = 1; u <= n; ++u)
        if (deg[u] > 0) {
            start = u;
            break;
        }
    if (start == 0) { // no edges: the empty graph admits an Euler circuit
        circleExist = true;
        return 1;
    }
    for (int u = 1; u <= n; ++u)
        if (deg[u] > 0 && dsu.find(u) != dsu.find(start)) return 0;

    int odd = 0, oddV = 0;
    for (int u = 1; u <= n; ++u)
        if (deg[u] % 2) {
            ++odd;
            oddV = u;
        }
    if (odd == 0) {
        circleExist = true;
        return start;
    }
    if (odd == 2) return oddV;
    return 0;
}

std::vector<int> Graph::getEuleranTourFleri() const {
    std::vector<int> tour;
    bool circleExist = false;
    int start = checkEuler(circleExist);
    if (start == 0) return tour;

    auto g = toAdjList();
    int total = 0;
    for (int u = 1; u <= n; ++u) total += (int)g[u].size();
    total /= 2;

    int cur = start;
    tour.push_back(cur);
    for (int step = 0; step < total; ++step) {
        int next = -1, nextW = 0;
        for (auto& e : g[cur]) {
            if (!isBridge(g, cur, e.first, e.second)) {
                next = e.first;
                nextW = e.second;
                break;
            }
            if (next == -1) { // remember a bridge as fallback only
                next = e.first;
                nextW = e.second;
            }
        }
        if (next == -1) {
            tour.clear();
            return tour;
        }
        g[cur].erase({next, nextW});
        g[next].erase({cur, nextW});
        cur = next;
        tour.push_back(cur);
    }
    return tour;
}

std::vector<int> Graph::getEuleranTourEffective() const {
    std::vector<int> tour;
    bool circleExist = false;
    int start = checkEuler(circleExist);
    if (start == 0) return tour;

    auto g = toAdjList();
    long long total = 0;
    for (int u = 1; u <= n; ++u) total += (long long)g[u].size();
    total /= 2;

    std::vector<int> order;
    std::stack<int> st;
    st.push(start);
    long long used = 0;
    while (!st.empty()) {
        int u = st.top();
        if (g[u].empty()) {
            order.push_back(u);
            st.pop();
        } else {
            auto it = g[u].begin();
            int v = it->first, w = it->second;
            g[u].erase(it);
            auto jt = g[v].lower_bound({u, INT_MIN});
            if (jt != g[v].end() && jt->first == u && jt->second == w) g[v].erase(jt);
            st.push(v);
            ++used;
        }
    }

    if (used != total) return std::vector<int>();
    std::reverse(order.begin(), order.end());
    return order;
}