N6

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
using namespace std;

bool bfs(vector<vector<int>>& graph, vector<int>& parent, int start, int end)
{
    int len = graph.size();
    vector<bool> visited(len, 0);
    queue<int> q;

    visited[start] = 1;
    parent[start] = -1;
    q.push(start);

    while (!q.empty())
    {
        int v = q.front();
        q.pop();

        for (int u = 0; u < len; ++u)
        {
            if (!visited[u] && graph[v][u] != 0)
            {
                if (u == end)
                {
                    parent[u] = v;
                    return 1;
                }

                visited[u] = 1;
                parent[u] = v;
                q.push(u);
            }
        }
    }
    return 0;
}

int fordFulkerson(vector<vector<int>>& graph, int start, int end)
{
    int max_flow = 0;
    vector<vector<int>> resNet = graph;
    vector<int> parent(graph.size(), 0);

    while (bfs(resNet, parent, start, end))
    {
        int path_flow = INT_MAX;

        for (int v = end; v != start; v = parent[v])
        {
            int u = parent[v];
            path_flow = min(path_flow, resNet[u][v]);

        }

        for (int v = end; v != start; v = parent[v])
        {
            int u = parent[v];
            resNet[u][v] -= path_flow;
            resNet[v][u] += path_flow;

        }


        max_flow += path_flow;
    }

    return max_flow;
}


bool ham_cycle(vector<vector<int>>& graph, vector<int>& path, vector<int>& visited, int start)
{
    int len = graph.size();
    path.push_back(start);

    if (path.size() == len)
    {
        if (graph[path[0]][path.back()])
            return 1;
        else
        {
            path.pop_back();
            return 0;
        }
    }

    visited[start] = 1;
    for (int i = 0; i < len; ++i)
        if (!visited[i] && graph[start][i] != 0)
            if (ham_cycle(graph, path, visited, i))
                return 1;

    visited[start] = 0;
    path.pop_back();

    return 0;
}

vector<int> coloring(vector<vector<int>>& graph)
{
    int len = graph.size();
    vector<int> result(len, -1);
    vector<int> avaliable(len, 0);

    result[0] = 0;

    for (int i = 1; i < len; ++i)
    {
        for (int it : graph[i])
            if (result[it] != -1)
                avaliable[it] = 1;


        int color;
        for (color = 0; color < len; ++color)
            if (!avaliable[color])
                break;

        result[i] = color;
    }

    return result;
}


int main()
{
    vector<vector<int>> graph = { { 0, 5, 6, 6, 6, 4, 5, 0, 0, 8, 8, 4, 4 },
                                { 5, 0, 8, 0, 3, 8, 4, 8, 6, 6, 6, 3, 4 },
                                { 6, 8, 0, 2, 0, 0, 0, 9, 3, 5, 3, 8, 1 },
                                { 6, 0, 2, 0, 2, 4, 7, 7, 7, 9, 5, 5, 5 },
                                { 6, 3, 0, 2, 0, 1, 5, 5, 4, 4, 1, 4, 2 },
                                { 4, 8, 0, 4, 1, 0, 8, 1, 5, 4, 5, 8, 6 },
                                { 5, 4, 0, 7, 5, 8, 0, 6, 9, 0, 1, 2, 0 },
                                { 0, 8, 9, 7, 5, 1, 6, 0, 4, 6, 7, 3, 3 },
                                { 0, 6, 3, 7, 4, 5, 9, 4, 0, 4, 4, 1, 1 },
                                { 8, 6, 5, 9, 4, 4, 0, 6, 4, 0, 9, 2, 7 },
                                { 8, 6, 3, 5, 1, 5, 1, 7, 4, 9, 0, 6, 9 },
                                { 4, 3, 8, 5, 4, 8, 2, 3, 1, 2, 6, 0, 3 },
                                { 4, 4, 1, 5, 2, 6, 0, 3, 1, 7, 9, 3, 0 } };


    int max_flow = fordFulkerson(graph, 0, graph.size()-1);
    cout << "Max flow: " << max_flow << '\n';

    vector<int> visited(graph.size(), 0);
    vector<int> path;

    ham_cycle(graph, path, visited, 0);

    cout << "Hamilton Cycle:\n";
    for (int it : path)
        cout << it << " ";
    cout << '\n';

    vector<int> rez = coloring(graph);

    for (int i = 0; i < graph.size(); ++i)
        cout << i << "--->" << rez[i] << '\n';


    return 0;
}