// Find max distance for each vertex in graph
#include <iostream>
#include <vector>
#include <queue>

size_t* maxDist(bool** m, const size_t& size);
size_t maxDistUtil(bool** m, const size_t& v, const size_t& size);
std::vector<size_t> adjVertices(bool** m, const size_t& v, const size_t& size);


int main() {
    // ADJACENCY MATRIX EMULATION
    constexpr size_t n = 5;
    bool** matrix = new bool* [n]{};
    for (size_t i = 0; i < n; ++i)
        matrix[i] = new bool[n]{};

    matrix[0][1] = matrix[1][0] = true;
    matrix[0][2] = matrix[2][0] = true;
    matrix[1][2] = matrix[2][1] = true;
    matrix[2][4] = matrix[4][2] = true;
    matrix[3][4] = matrix[4][3] = true;
    // 0 1 1 0 0
    // 1 0 1 0 0
    // 1 1 0 0 1
    // 0 0 0 0 1
    // 0 0 1 1 0
    ///////////////////////////////

    size_t* resultM = maxDist(matrix, n);
    for (size_t i = 0; i < n; ++i)
        std::cout << i << ": " << resultM[i] << std::endl;

    system("pause");
    return 0;
}

size_t* maxDist(bool** m, const size_t& size) {
    size_t* resDist = new size_t[size];
    for (size_t i = 0; i < size; ++i) {
        resDist[i] = maxDistUtil(m, i, size);
    }
    return resDist;
}

size_t maxDistUtil(bool** m, const size_t& v, const size_t& size) {
    bool* visited = new bool[size] {};
    visited[v] = true;

    size_t dist = 0;
    std::queue<size_t> stack;
    for (auto&& i : adjVertices(m, v, size))
        stack.push(i);

    while (!stack.empty()) {
        size_t& p = stack.front();
        stack.pop();


        for (auto&& i : adjVertices(m, p, size)) {
            if (!visited[i]) {
                visited[i] = true;
                stack.push(i);
                ++dist;
            }
        }
        visited[p] = true;
    }
    delete[]visited;
    return dist;
}

std::vector<size_t> adjVertices(bool** m, const size_t& v, const size_t& size) {
    std::vector<size_t> adj;
    for (size_t i = 0; i < size; ++i)
        if (m[v][i])
            adj.push_back(i);
    return adj;
}