#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <memory>
#include "UnionFindSet.h"
#include <set>
using namespace std;

namespace matrix
{
    // V : vertice 数据顶点
    // W : weight  权重,
    // Direction: 判断图类型
    template <class V, class W, W INT_MAX = INT32_MAX, bool Direction = false>
    class Graph
    {
    public:
        // 我们手动输入权值
        Graph(const V *vertice, size_t n)
        {
            for (int i = 0; i < n; i++)
            {
                _vertices.push_back(vertice[i]);
                // 构建顶点与下标的映射关系
                _vertice_index[vertice[i]] = i;
            }

            _matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                _matrix[i].resize(n, INT_MAX);
            }
        }

        size_t GetIndex(const V &v)
        {
            auto it = _vertice_index.find(v);
            if (it == _vertice_index.end())
            {
                // 顶点指针错误
                // assert(1);
                return -1;
            }
            return it->second;
        }

        // 手动添加顶点间关系，并赋权值
        // 约定一下：有向是左 -> 右
        void addedge(const V &v1, const V &v2, const W weight)
        {
            auto v1_index = GetIndex(v1);
            auto v2_index = GetIndex(v2);
            // 无向图
            if (Direction == false)
            {
                _matrix[v1_index][v2_index] = weight;
                _matrix[v2_index][v1_index] = weight;
            }
            else // 有向，则修改v2的坐标
            {
                _matrix[v1_index][v2_index] = weight;
            }
        }

        void size_t_addedge(size_t v1, size_t v2, const W weight)
        {
            // 无向图
            if (Direction == false)
            {
                _matrix[v1][v2] = weight;
                _matrix[v2][v1] = weight;
            }
            else // 有向，则修改v2的坐标
            {
                _matrix[v2][v1] = weight;
            }
        }

        void showgrapth()
        {
            int n = 0;
            cout << "\t";
            for (int i = 0; i < _vertices.size(); i++)
                cout << i << "\t";

            cout << endl;
            for (auto i : _matrix)
            {
                cout << n++ << "\t";
                for (auto n : i)
                {
                    if (n == INT32_MAX)
                        cout << "*" << "\t";
                    else
                        cout << n << "\t";
                }
                cout << endl;
            }
        }

        // 层序遍历————默认从0开始层序遍历
        void BFS(const V &v)
        {
            auto index = GetIndex(v);

            queue<int> q;
            vector<bool> _set(_vertices.size(), false);

            q.push(index);
            cout << _vertices[index] << "->";
            _set[index] = true;
            while (q.empty() != true)
            {
                int tmp = q.front();
                q.pop();
                // 获取所有连接点,并判断载入队列
                int time = 0;
                while (time < _matrix[tmp].size())
                {
                    if (_matrix[tmp][time] != INT_MAX && _set[time] == false)
                    {
                        q.push(time);
                        cout << _vertices[time] << " ";
                        _set[time] = true;
                    }
                    time++;
                }
                cout << "->";
            }
            cout << endl;
        }

        void _dfs(int index, vector<bool> &_set)
        {
            cout << _vertices[index] << "--";
            for (int i = 0; i < _matrix[index].size(); i++)
            {
                if (_set[i] != true && _matrix[index][i] != INT_MAX)
                {
                    _set[i] = true;
                    _dfs(i, _set);
                }
            }
        }

        void DFS(const V &v)
        {
            auto index = GetIndex(v);
            vector<bool> _set(_vertices.size(), false);
            _set[index] = true;
            _dfs(index, _set);
            cout << endl;
        }

        struct edge
        {
            size_t _v1;
            size_t _v2;
            W _w;

            edge(size_t v1, size_t v2, W w)
                : _v1(v1), _v2(v2), _w(w)
            {
            }

            bool operator>(const edge &v1) const
            {
                return _w > v1._w;
            }
        };

        W Kruskal(Graph<V, W> &minfree)
        {
            priority_queue<edge, vector<edge>, greater<edge>> greater_queue;
            // 队列载入边信息
            for (int i = 0; i < _matrix.size(); i++)
            {
                for (int j = 0; j < _matrix[i].size(); j++)
                {
                    if (i >= j && _matrix[i][j] != INT_MAX)
                        greater_queue.push(edge(i, j, _matrix[i][j]));
                }
            }

            size_t sum_edge = 0;
            W sum_w = W();
            UnionFindSet it(_vertices.size());

            int time = _vertices.size() - 1;

            while (sum_edge < time)
            {
                edge tmp = greater_queue.top();
                if (it.IsSameRoot(tmp._v1, tmp._v2))
                {
                    greater_queue.pop();
                    continue;
                }
                cout << _vertices[tmp._v1] << "->" << _vertices[tmp._v2] << ": " << tmp._w << endl;
                // 单独构建一个外部最小生成树
                minfree.size_t_addedge(tmp._v1, tmp._v2, tmp._w);
                it._union(tmp._v1, tmp._v2);
                greater_queue.pop();
                sum_w += tmp._w;
                sum_edge++;
            }

            // cout << "w : " << sum_w << endl;
            // cout << "sum_edge : " << sum_edge << endl;
            // cout << "_vertice : " << _vertices.size() << endl;

            // 经过n - 1次连接边，如果所有顶点都在树中，则有最小生成树；
            // 如何判断？ 并查集，由于我们实现了压缩路径算法，所以所有孩子只有一个根。
            int root = it.GetRoot(0);
            for (int i = 1; i < it.size(); i++)
            {
                // 如果根不相同，说明还有孤岛顶点，即不是最小生成树
                if (root != it.GetRoot(i))
                    return W();
            }
            return sum_w;
        }

        W Prim(Graph<V, W> &minfree, const V &start)
        {
            size_t ptr = GetIndex(start);
            set<size_t> X;
            set<size_t> Y;
            for (int i = 0; i < _vertices.size(); i++)
                Y.insert(i);

            priority_queue<edge, vector<edge>, greater<edge>> greater_queue;

            // 先载入开始顶点
            X.insert(ptr);
            Y.erase(ptr);
            // 队列载入与顶点相连边的顶点信息
            for (int i = 0; i < _matrix.size(); i++)
            {
                if (_matrix[ptr][i] != INT_MAX)
                    greater_queue.push(edge(ptr, i, _matrix[ptr][i]));
            }

            size_t edge_sum = 0;
            W w_sum = 0;

            while (greater_queue.empty() != true)
            {
                edge tmp = greater_queue.top();
                if (X.find(tmp._v1) != X.end() && X.find(tmp._v2) != X.end())
                {
                    greater_queue.pop();
                    continue;
                }
                // 不都在X中都载入
                size_t new_X;
                if (X.find(tmp._v1) == X.end())
                    new_X = tmp._v1;
                else
                    new_X = tmp._v2;
                // cout << _vertices[tmp._v1] << "->" << _vertices[tmp._v2] << ": " << tmp._w << endl;
                minfree.size_t_addedge(tmp._v1, tmp._v2, tmp._w);
                greater_queue.pop();
                w_sum += tmp._w;
                edge_sum++;
                X.insert(new_X);
                Y.erase(new_X);

                for (int i = 0; i < _matrix.size(); i++)
                {
                    if (_matrix[new_X][i] != INT_MAX)
                        greater_queue.push(edge(new_X, i, _matrix[new_X][i]));
                }
            }

            // cout << "w : " << w_sum << endl;
            // cout << "sum_edge : " << edge_sum << endl;
            // cout << "_vertice : " << _vertices.size() << endl;
            if (edge_sum != _vertices.size() - 1)
                return W();
            return w_sum;
        }

        // 最短路径
        void Dijkstra(const V &v)
        {
            vector<W> dij_vec(_vertices.size(), INT_MAX);
            vector<bool> exist(_vertices.size(), true);

            int exist_sum = _vertices.size();
            auto start_index = GetIndex(v);

            dij_vec[start_index] = 0;
            exist[start_index] = false;
            exist_sum--;

            while (exist_sum > 0)
            {
                // 在未被标记顶点内寻找
                for (int i = 0; i < _matrix[start_index].size(); i++)
                {
                    if (exist[i] && _matrix[start_index][i] != INT_MAX)
                    {
                        dij_vec[i] = min(dij_vec[i], (_matrix[start_index][i] + dij_vec[start_index]));
                    }
                }
                // 开始删除目前最小值
                // 获取最小值下标
                int index = -1;
                size_t min_index = INT_MAX;
                for (int i = 0; i < dij_vec.size(); i++)
                {
                    if (exist[i] && dij_vec[i] < min_index)
                    {
                        min_index = dij_vec[i];
                        index = i;
                    }
                }
                // 删除已经确定的顶点
                if (index != -1)
                {
                    //    cout << "delete: " << _vertices[index] << endl;
                    exist[index] = false;
                    start_index = index;
                    exist_sum--;
                }
            }

            cout << "结果：" << endl;
            for (int i = 0; i < dij_vec.size(); i++)
            {
                cout << _vertices[i] << " min:" << dij_vec[i] << endl;
            }
        }

        bool Bellman_Ford(const V &v)
        {
            vector<W> bell_vec(_vertices.size(), INT_MAX);
            vector<size_t> last_index(_vertices.size(), -1);
            auto start_index = GetIndex(v);

            bell_vec[start_index] = 0;
            last_index[start_index] = 0;
            int n = _vertices.size();

            for (int z = 0; z < n; z++)
            {
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (_matrix[i][j] != INT_MAX && bell_vec[i] + _matrix[i][j] < bell_vec[j])
                        {
                            bell_vec[j] = bell_vec[i] + _matrix[i][j];
                            last_index[j] = i;
                        }
                    }
                }
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (_matrix[i][j] != INT_MAX && bell_vec[i] + _matrix[i][j] < bell_vec[j])
                    {
                        return false;
                    }
                }
            }

            cout << "结果：" << endl;
            for (int i = 0; i < n; i++)
            {
                cout << _vertices[i] << " min:" << bell_vec[i] << endl;
            }

            return true;
        }

        void Floyd_warshall()
        {
            vector<vector<W>> dis;
            vector<vector<int>> parentpath;
            int n = _vertices.size();

            dis.resize(n);
            parentpath.resize(n);
            // 初始化权值图
            // 初始化父路径图
            for (int i = 0; i < n; i++)
            {
                dis[i].resize(n, INT_MAX);
                parentpath[i].resize(n, -1);
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (_matrix[i][j] != INT_MAX)
                    {
                        dis[i][j] = _matrix[i][j];
                        // 默认i->j就是最短路径，所以j的上一级就是i
                        parentpath[i][j] = i;
                    }

                    if (i == j)
                        dis[i][j] = 0;
                }   
            }

            // 用k作为中转点，试图获取i->k->j的最短路径
            for (int k = 0; k < n; k++)
            {
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (dis[i][k] != INT_MAX && dis[k][j] != INT_MAX && dis[i][k] + dis[k][j] < dis[i][j])
                        {
                            dis[i][j] = dis[i][k] + dis[k][j];
                            parentpath[i][j] = parentpath[k][j];
                        }
                    }
                }
            }

            cout << "结果：" << endl;
            for (int i = 0; i < n; i++)
            {
                cout << _vertices[i] << " min:" << endl;
                for (int j = 0; j < n; j++)
                {
                    cout << _vertices[j] << ":" << dis[i][j] << " ";
                }
                cout << endl;
            }
        }

    private:
        vector<V> _vertices;        // 储存顶点, O(1)获取顶点信息
        map<V, int> _vertice_index; // 通过key与数组下标构建映射关系，是上面O(1)获取顶点效率的前提。
        vector<vector<W>> _matrix;  // 矩阵构建连接及权值信息。
    };
}

namespace list
{
    template <class W, W INT_MAX = INT32_MAX>
    struct V_Node
    {
        int _index;
        // 权值
        W _weigth;
        V_Node<W> *_next;

        V_Node(int index, const W &weigth = INT_MAX, V_Node<W> *next = nullptr)
            : _index(index), _weigth(weigth), _next(next)
        {
        }

        V_Node<W> *GetLast()
        {
            if (_next == nullptr)
                return this;

            V_Node<W> *tmp = _next;
            while (tmp->_next != nullptr)
                tmp = tmp->_next;
            return tmp;
        }
    };

    template <class V, class W, W INT_MAX = INT32_MAX, bool Direction = false>
    class Graph
    {
    public:
        typedef V_Node<W> v_node;

        Graph(const V *vertice, size_t n)
        {
            for (int i = 0; i < n; i++)
            {
                _vertices.push_back(vertice[i]);
                // 构建顶点与下标的映射关系
                _vertice_index[vertice[i]] = i;
            }

            for (int i = 0; i < n; i++)
            {
                _list.push_back(new v_node(i));
            }
        }

        ~Graph()
        {
            // 真想用智能指针来负责析构，但类型出错真烦
        }

        size_t GetIndex(const V &v)
        {
            auto it = _vertice_index.find(v);
            if (it == _vertice_index.end())
            {
                // 顶点指针错误
                // assert(1);
                return -1;
            }
            return it->second;
        }

        // 手动添加全值
        // 约定一下：有向是左 -> 右
        void addedge(const V &v1, const V &v2, const W weight)
        {
            auto v1_index = GetIndex(v1);
            auto v2_index = GetIndex(v2);
            // 无向图
            if (Direction == false)
            {
                _list[v1_index]->GetLast()->_next = new v_node(v2_index, weight);
                _list[v2_index]->GetLast()->_next = new v_node(v1_index, weight);
            }
            else // 有向图
            {
                _list[v1_index]->GetLast()->_next = new v_node(v2_index, weight);
                ;
            }
        }

        void showgrapth()
        {
            for (auto i : _list)
            {
                cout << _vertices[i->_index] << "(w:" << i->_weigth << ")" << "-->";
                while (i->_next != nullptr)
                {
                    i = i->_next;
                    cout << _vertices[i->_index] << "(w:" << i->_weigth << ")" << "->";
                }
                cout << endl;
            }
        }

    private:
        vector<V> _vertices;
        map<V, int> _vertice_index;
        vector<v_node *> _list;
    };

}