#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

const int INF = 1000 * 1000 * 1000;

class Graph
{
public:
    map<int, vector<pair<int, int>>> g;
    bool directed;
    bool weighted;
    int s, t; // для сети

    Graph()
    {
        directed = false;
        weighted = false;
    }

    Graph(int source, int stock, const string& path)
    { // сеть
        s = source;
        t = stock;
        ifstream in(path.c_str());

        in >> directed >> weighted; // сначала в инпуте указывается, ориентирован и взвешен ли граф
                                    // (0 если нет, 1 если да)

                                    /* Далее в инпуте указываются четыре команды:
                                    +v i добавляет вершину i
                                    -v i удаляет вершину i и все инцидентные ей ребра
                                    +e i j w добавляет ребро (либо дугу) между i и j, и если граф взвешенный, делает его весом
                                    w.
                                    -e i j удаляет ребро между i и j
                                    */
        while (!in.eof())
        {
            string str;
            in >> str;
            if (str == "+v")
            {
                int v;
                in >> v;
                add_vertex(v);
            }
            else if (str == "+e")
            {
                int i, j, w = 1; // если граф не взвешен, по умолчанию весом ребра считаем 1.
                in >> i >> j;
                if (weighted)
                {
                    in >> w;
                }
                add_edge(i, j, w);
            }
            else if (str == "-e")
            {
                int i, j;
                in >> i >> j;
                remove_edge(i, j);
            }
            else if (str == "-v")
            {
                int v;
                in >> v;
                remove_vertex(v);
            }
        }

        in.close();
    }

    Graph(int n)
    { // тестовый граф (будем создавать полный граф)
        weighted = false;
        directed = false;
        for (int i = 0; i < n; i++)
        {
            add_vertex(i);
            for (int j = 0; j < i; j++)
            {
                add_edge(i, j, 1);
            }
        }
    }

    Graph(const map<int, vector<pair<int, int>>>& a)
    { // copy
        g = a;
    }

    Graph(const string& path)
    { // read from file
        ifstream in(path.c_str());

        in >> directed >> weighted; // сначала в инпуте указывается, ориентирован и взвешен ли граф
                                    // (0 если нет, 1 если да)

                                    /* Далее в инпуте указываются четыре команды:
                                    +v i добавляет вершину i
                                    -v i удаляет вершину i и все инцидентные ей ребра
                                    +e i j w добавляет ребро (либо дугу) между i и j, и если граф взвешенный, делает его весом
                                    w.
                                    -e i j удаляет ребро между i и j
                                    */
        while (!in.eof())
        {
            string s;
            in >> s;
            if (s == "+v")
            {
                int v;
                in >> v;
                add_vertex(v);
            }
            else if (s == "+e")
            {
                int i, j, w = 1; // если граф не взвешен, по умолчанию весом ребра считаем 1.
                in >> i >> j;
                if (weighted)
                {
                    in >> w;
                }
                add_edge(i, j, w);
            }
            else if (s == "-e")
            {
                int i, j;
                in >> i >> j;
                remove_edge(i, j);
            }
            else if (s == "-v")
            {
                int v;
                in >> v;
                remove_vertex(v);
            }
        }

        in.close();
    }

    ~Graph()
    {
        g.clear();
    }

    void add_vertex(int v)
    {
        if (g.find(v) == g.end())
        { // если вершины еще нет в графе, то добавляем
            vector<pair<int, int>> tmp;
            g[v] = tmp;
        }
    }

    void add_edge(int u, int v, int w)
    {
        if (g.find(u) == g.end() || g.find(v) == g.end())
        { // если таких вершин нет - выходим
            return;
        }

        for (int i = 0; i < g[u].size(); i++)
        {
            if (g[u][i].first == v)
            { // если ребро (u, v) уже существует, то выходим
                return;
            }
        }

        g[u].push_back(make_pair(v, w));

        if (!directed)
        {
            add_edge(v, u, w);
        }
    }

    void remove_edge(int u, int v)
    {
        if (g.find(u) == g.end() || g.find(v) == g.end())
        {
            return;
        }
        for (int i = 0; i < g[u].size(); i++)
        { // ищем все ребра (u, v)
            if (g[u][i].first == v)
            {
                g[u].erase(g[u].begin() + i);
            }
        }

        if (!directed)
        { // если граф неориентир, то надо так же удалить все ребра (v, u)
            remove_edge(v, u);
        }
    }

    void remove_vertex(int v)
    {
        if (g.find(v) == g.end())
        {
            return;
        }
        g.erase(v);

        for (map<int, vector<pair<int, int>>>::iterator it = g.begin(); it != g.end(); it++)
        { // после удаления вершины v проходимся по всем остальным вершинам i и
            remove_edge((*it).first, v); // ищем все ребра типа (i, v) и удаляем их
        }
    }

    Graph transponate()
    {
        if (!directed)
        {
            return Graph(g);
        }
        Graph result;
        result = Graph();
        result.directed = true;
        result.weighted = weighted;

        for (map<int, vector<pair<int, int>>>::iterator it = g.begin(); it != g.end(); it++)
        {
            result.add_vertex((*it).first);
            for (int i = 0; i < int((*it).second.size()); i++)
            {
                result.add_vertex(g[(*it).first][i].first);
                result.add_edge(g[(*it).first][i].first, (*it).first, g[(*it).first][i].second);
            }
        }

        return result;
    }

    void print(string& path)
    {
        ofstream out;
        out.open(path.c_str());

        cout << g.size() << endl; // количество вершин в графе
        for (map<int, vector<pair<int, int>>>::iterator it = g.begin(); it != g.end(); it++)
        {
            for (int i = 0; i < int(((*it).second).size()); i++)
            { // печатаем все ребра (если граф неориентированный, print напечатает ребра (i, j) и
              // (j, i))
                out << (*it).first << " " << g[(*it).first][i].first;
                if (weighted)
                {
                    out << " "
                        << g[(*it).first][i].second; // добавляем вес ребра, если граф взвешен
                }
                out << endl;
            }
        }
        out.close();
    }
};

class GraphFunctions
{
private:
    Graph g;

public:
    GraphFunctions()
    {
    }

    GraphFunctions(const Graph& graph)
    {
        g = graph;
    }

    /* Задание 1b вариант 3.*/
    Graph graph_union(Graph a)
    {
        Graph result;
        result = Graph(); // создаем пустой граф

        if (a.directed != g.directed || a.weighted != g.weighted)
        { // если графы не совпадают друг с другом, то вернуть пустой граф
            return result;
        }
        result.directed = g.directed;
        result.weighted = g.weighted;

        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            result.add_vertex((*it).first);
            for (int i = 0; i < int(((*it).second).size()); i++)
            {
                result.add_edge((*it).first, g.g[(*it).first][i].first, g.g[(*it).first][i].second);
            }
        }
        for (map<int, vector<pair<int, int>>>::iterator it = a.g.begin(); it != a.g.end(); it++)
        {
            result.add_vertex((*it).first);
            for (int i = 0; i < int(((*it).second).size()); i++)
            {
                result.add_edge((*it).first, a.g[(*it).first][i].first, a.g[(*it).first][i].second);
            }
        }

        return result;
    }



    /* Задание 2 вариант 5.
    https://e-maxx.ru/algo/connected_components. */
    map<int, bool> empty_used()
    {
        map<int, bool> used;
        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            used[(*it).first] = false;
        }
        return used;
    }

    void dfs1(int v, Graph& g, map<int, bool>& used, vector<int>& order)
    {
        used[v] = true;
        for (int i = 0; i < g.g[v].size(); i++)
        {
            if (!used[g.g[v][i].first])
            {
                dfs1(g.g[v][i].first, g, used, order);
            }
        }
        order.push_back(v);
    }

    void dfs2(int v, Graph& gt, map<int, bool>& used)
    {
        used[v] = true;
        for (int i = 0; i < gt.g[v].size(); i++)
        {
            if (!used[gt.g[v][i].first])
            {
                dfs2(gt.g[v][i].first, gt, used);
            }
        }
    }

    int comp_count()
    {
        int result = 0;
        Graph gt = g.transponate();
        vector<int> order;

        map<int, bool> used = empty_used();
        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            /*Запускаем серию обходов в глубину графа G, которая возвращает
            вершины в порядке увеличения времени выхода, т.е.некоторый список order.*/
            if (!used[(*it).first])
            {
                dfs1((*it).first, g, used, order);
                result++;
            }
        }
        return result;
    }

    /* Задание 3.
    Алгоритм Прима:
    https://ru.wikipedia.org/wiki/Алгоритм_Прима
    */
    Graph prim()
    {
        Graph mst;
        mst = Graph();
        mst.directed = false;
        mst.weighted = true;

        map<int, bool> used; // индикатор, включена ли вершина в mst или нет.
        map<int, int> min_w; // хранит вес наименьшего инцидентного ребра из вершины i
        map<int, int> sel_e; // для вершины i содержит конец этого наименьшего ребра

        int start = -1;
        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            int v = (*it).first;
            if (start == -1)
            { // поскольку в алгоритме Прима в качестве начальной вершины выбирается любая
                start = v; // то для облегчения задачи выберем первую попавшуюся вершину
            }
            used[v] = false; // изначально все ребра не в mst
            min_w[v] = INF; // расстояние до всех вершин неизвестно <=> равно бесконечности
            sel_e[v] = -1; // исходя из строки выше, концы ребер неизвестны <=> равны -1
        }

        min_w[start] = 0; // наименьший вес от стартовой вершины до стартовой = 0
        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        { // проходим по всем вершинам
            int v = -1; // выбираем следующую вершину вне mst(наше дерево), которую включим в mst, с минимальным
                        // весом (цикл ниже)
            for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
            {
                if (!used[(*it).first] && (v == -1 || min_w[(*it).first] < min_w[v]))
                {
                    v = (*it).first;
                }
            }
            if (min_w[v] == INF)
            {
                return Graph();
            }

            used[v] = true; // добавляем вершину v в mst
            if (sel_e[v] != -1)
            { // если для вершины v уже посчитан конец наименьшего ребра
                mst.add_vertex(v);
                mst.add_vertex(sel_e[v]);
                mst.add_edge(v, sel_e[v], min_w[v]); // то добавляем это ребро в ответ
            }
            for (int i = 0; i < g.g[v].size(); i++)
            { // для всех соседей v пересчитываем min_w и sel_e по возможности
                if (g.g[v][i].second < min_w[g.g[v][i].first])
                { // если вес ребра (v, сосед v) меньше значения в min_w
                    min_w[g.g[v][i].first] = g.g[v][i].second; // то обновляем значение min_w
                    sel_e[g.g[v][i].first]
                        = v; // и для соседа v указываем концов наименьшего ребра само v
                }
            }
        }

        return mst;
    }



    /* Задание 4а. По условию подходит алгоритм Дейкстра - он не работает при отрицательных ребрах.*/
    pair<int, vector<int>> dijkstra(int s, int t)
    {
        vector<int> path;

        map<int, int> d; // расстояние до вершины от старта
        map<int, int> p; // "родитель" вершины в кратчайшем пути от старта
        map<int, bool> used; // непосещенность вершины

        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            int v = (*it).first;
            d[v] = INF; // изначально кратчайшего пути нет <=> расстояние равно бесконечности
            p[v] = -1;
            used[v] = false;
        }

        d[s] = 0;
        p[s] = s; // родитель старта - сама стартовая вершина
        for (int i = 0; i < g.g.size(); i++)
        {
            int v = -1;
            for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
            {
                if (!used[(*it).first] && (v == -1 || d[(*it).first] < d[v]))
                {
                    //выбирается вершина v с наименьшей величиной среди ещё не помеченных, т.е.:
                    v = (*it).first;
                }
            }

            if (d[v] == INF) //Если расстояние до выбранной вершины v оказывается равным бесконечности, то алгоритм останавливается
            {
                break;
            }

            used[v] = true;
            for (int i = 0; i < g.g[v].size(); i++) //Иначе вершина помечается как помеченная, и просматриваются все рёбра, исходящие из данной вершины
            {
                if (d[g.g[v][i].first] > d[v] + g.g[v][i].second) //Если релаксация успешна(т.е.расстояние d[to] меняется),
                {
                    d[g.g[v][i].first] = d[v] + g.g[v][i].second; //то пересчитывается расстояние d[]
                    p[g.g[v][i].first] = v;//и сохраняется предок p[].
                }
            }
        }

        /*if (p[t] == -1)
        {
        return make_pair(-1, path);
        }*/
        int cur = t;
        while (cur != s)
        {
            path.push_back(cur);
            cur = p[cur];
        }
        path.push_back(cur);

        reverse(path.begin(),
            path.end()); // так как в массив путь добавлялся от конца в начало, надо его перевернуть
        return make_pair(d[t], path);
    }

    /*Задание 4b. Здесь под условия подходит алгоритм Флойда
    http://e-maxx.ru/algo/floyd_warshall_algorithm*/

    void floyd(map<int, map<int, int>>& d, map<int, map<int, int>>& next)
    {
        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            map<int, int> tmp, tmp2;
            d[(*it).first] = tmp;
            next[(*it).first] = tmp2;
            for (map<int, vector<pair<int, int>>>::iterator it2 = g.g.begin(); it2 != g.g.end();
                it2++)
            {
                d[(*it).first][(*it2).first] = INF; // сначала все вершины недостижимы
                next[(*it).first][(*it2).first] = -1;
            }
        }
        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            d[(*it).first][(*it).first] = 0;
            for (int i = 0; i < g.g[(*it).first].size(); i++)
            {
                d[(*it).first][g.g[(*it).first][i].first]
                    = g.g[(*it).first][i].second; // задаем d все заданные веса ребер (d(i,j) равна весу ребра между i и j)
                next[(*it).first][g.g[(*it).first][i].first] = g.g[(*it).first][i].first;
            }
        }
        /*Все, что мы делаем, это мы для каждой вершины i и j проверяем,
        нет ли такого пути через вершину k, такой, что путь i->k->j короче,
        чем текущий путь от i до j.Соответственно, все, что мы делаем,
        это проходимся по всем вершинам k от 1 до n - ной и проверяем для
        всех вершин i и j это условие.Если путь через k короче, чем текущая длина
        пути d(i, j), то мы обновляем это d(i, j) длиной пути через k.
        А next просто хранит предков для восстановления пути между i и j*/
        for (map<int, vector<pair<int, int>>>::iterator k = g.g.begin(); k != g.g.end(); k++)
        {
            for (map<int, vector<pair<int, int>>>::iterator i = g.g.begin(); i != g.g.end(); i++)
            {
                for (map<int, vector<pair<int, int>>>::iterator j = g.g.begin(); j != g.g.end();
                    j++)
                {
                    if (d[(*i).first][(*k).first] + d[(*k).first][(*j).first]
                        < d[(*i).first][(*j).first])
                    {
                        d[(*i).first][(*j).first]
                            = d[(*i).first][(*k).first] + d[(*k).first][(*j).first];
                        next[(*i).first][(*j).first] = next[(*i).first][(*k).first];
                    }
                }
            }
        }
    }

    /* Задание 4b. Классический алгоритм Форда-Беллмана c выводом отрицательного цикла
    http://e-maxx.ru/algo/ford_bellman
    */
    vector<int> ford_bellman(int s, map<int, int>& d)
    {
        d[s] = 0; // длина пути от стартовой вершины = 0
        int x;
        vector<int> negative_path;
        map<int, int> p;
        for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
        {
            p[(*it).first] = -1; // предки в путях инициализируются -1
        }
        p[s] = s;

        for (int k = 0; k < g.g.size(); ++k)
        {
            x = -1; // переменная сигнализирует о том, что найден цикл
            for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
            {
                int v = (*it).first; // проходим по всем вершинам от 0 до n - 1
                for (int j = 0; j < g.g[v].size(); j++) // проходим по соседям текущей вершины
                {
                    if (d[v] < INF) // если кратчайшее расстояние от s до текущей вершины уже найдено,
                    {
                        if (d[g.g[v][j].first] > d[v] + g.g[v][j].second) // то проверяем неравенство беллмана
                        {
                            d[g.g[v][j].first] = max(-INF, d[v] + g.g[v][j].second); // если оно не выполняется, то проводим релаксацию
                            p[g.g[v][j].first] = v; // родителем соседа назначаем текущую вершину
                            x = g.g[v][j].first;
                        }
                    }
                }
            }
        }

        if (x != -1) // если x не равно -1, то x содержит в себе стартовую вершину цикла отрицательного веса, поэтому выводим цикл
        {
            int y = x;
            for (int i = 0; i < g.g.size(); ++i)
            {
                y = p[y]; // проходим n раз по циклу
            }
            for (int cur = y;; cur = p[cur]) // начинаем от вершины y - вершины, находящейся в цикле
            {
                negative_path.push_back(cur);
                if (cur == y && negative_path.size() > 1) // если мы замкнули цикл (то есть cur равен вершине y, с которой мы
                                                          // стартовали, то выходим из цикла
                {
                    break;
                }
            }

            reverse(negative_path.begin(), negative_path.end()); // реверсим массив, куда добавлялся цикл
            return negative_path; // выводим непустой массив, содержащий цикл отрицательного веса
        }
        return negative_path; // иначе выводим пустой массив. Так как d передавалось ссылкой, так же мы получим после этого массив d
                              // длин кратчайших путей от s до всех остальных вершин.
    }

    /* Задание 5. Реализация алгоритма Форда-Фалкерсона с использованием dfs.

    https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину
    */
    // Cmin — пропускная способность в текущем подпотоке
    int ford_falkerson(int v, int Cmin, map<int, map<int, int>>& flow, map<int, bool>& used)
    {
        if (v == g.t)
        {
            return Cmin;
        }
        used[v] = true;
        for (int i = 0; i < g.g[v].size(); i++)
        {
            int u = g.g[v][i].first;
            int cap = g.g[v][i].second;
            if (!used[u] && cap > flow[v][u])
            {
                int delta = ford_falkerson(u, min(Cmin, cap - flow[v][u]), flow, used);
                if (delta > 0)
                {
                    //величина потока итеративно увеличивается посредством поиска увеличивающего
                    //пути(путь от источника s к стоку t, вдоль которого можно послать ненулевой поток).
                    flow[v][u] += delta;
                    flow[u][v] -= delta;
                    return delta;
                }
            }
        }
        return 0;
    }
};

int main()
{
    string in_path = "input.txt";
    string out_path = "output.txt";

    Graph g;
    GraphFunctions gf;

    // вывод графа

    //g = Graph(in_path);
    //g.print(out_path);


    // 1b задание 3 вариант

    /*g = Graph("input-1b-3-a.txt");
    Graph b("input-1b-3-b.txt");
    gf = GraphFunctions(g);
    gf.graph_union(b).print(out_path);*/

    // 2 задание 3 вариант

    /*g = Graph("input-2-3.txt");
    gf = GraphFunctions(g);
    int v;
    cin >> v;
    vector<int> result = gf.reachable_vertices(v);
    for (int i = 0; i < result.size(); i++)
    {
    cout << result[i] << " ";
    }
    cout << endl;*/

    // 2 задание 15 вариант

    g = Graph("input-2-5.txt");
    gf = GraphFunctions(g);
    cout << gf.comp_count() << endl;

    // 3 задание ПРИМА

    /*g = Graph("input-3.txt");
    gf = GraphFunctions(g);
    Graph mst = gf.prim();
    mst.print(out_path);*/

    // Задание 4b  4 вар

    //g = Graph("4b2.txt");
    ////g = Graph("input-4b.txt");
    //gf = GraphFunctions(g);
    //map<int, int> d;
    //for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
    //{
    //  d[(*it).first] = INF;
    //}
    //int u, v1, v2, n;
    //cin >> u >> v1 >> v2;
    //vector<int> result = gf.ford_bellman(u, d);
    //if (result.size() > 0)
    //{
    //  cout << "Found negative cycle: ";
    //  for (int i = 0; i < result.size(); i++)
    //  {
    //      cout << result[i] << " ";
    //  }
    //  cout << endl;
    //}
    //else
    //{
    //  cout << d[v1] << " " << d[v2] << endl;
    //}

    // Задание 4с 7 вар

    //g = Graph("input-4c.txt");
    //gf = GraphFunctions(g);
    //map<int, map<int, int>> d;
    ////d - это кратчайшиe расстояния между
    ////любыми двумя вершинами, то есть в итоге у нас каждое d(i, j) содержит длину кратчайшего расстояния
    //map<int, map<int, int>> next;
    //gf.floyd(d, next);
    //int v, n;
    //// n - судя по всему просто рандомное число, и мы смотрим, чтобы расстояние было больше.
    //cin >> v >> n;
    //for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
    //{
    //  int u = (*it).first;
    //
    //  if (d[v][u] == INF)//если ребра нет
    //  {
    //      //cout << -1 << endl;
    //      continue;
    //  }
    //  if (d[v][u] > n)
    //  {
    //      cout << v << " " << u << ":" << endl;
    //      cout << d[v][u] << endl;
    //  }
    //}

    // Задание 5

    /*int s, t;
    cin >> s >> t;
    g = Graph(s, t, "input-5.txt");
    gf = GraphFunctions(g);
    map<int, bool> used;
    map<int, map<int, int>> flow;
    for (map<int, vector<pair<int, int>>>::iterator it = g.g.begin(); it != g.g.end(); it++)
    {
        used[(*it).first] = false;
        for (map<int, vector<pair<int, int>>>::iterator it2 = g.g.begin(); it2 != g.g.end(); it2++)
        {
            flow[(*it).first][(*it2).first] = 0;
        }
    }
    int max_result = 0, max_flow = 0;
    while ((max_result = gf.ford_falkerson(s, INF, flow, used)) > 0)
    {
        used = gf.empty_used();
        max_flow += max_result;
    }
    cout << max_flow << endl;
    for (map<int, map<int, int>>::iterator it = flow.begin(); it != flow.end(); it++)
    {
        int v = (*it).first;
        for (int i = 0; i < g.g[v].size(); i++)
        {
            cout << v << " " << g.g[v][i].first << " " << flow[v][g.g[v][i].first] << "/"
                << g.g[v][i].second << endl;
        }
    }*/

    system("pause");
}