// 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, bool* visited);


int main() {
    // ADJACENCY MATRIX EMULATION
    constexpr size_t n = 6;
    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][3] = matrix[3][1] = true;
    matrix[1][4] = matrix[4][1] = true;
    matrix[4][5] = matrix[5][4] = true;

    //0 1 1 0 0 0
    //1 0 0 1 1 0
    //1 0 0 0 0 0
    //0 1 0 0 0 0
    //0 1 0 0 0 1
    //0 0 0 0 1 0
    /////////////////////////////////


    //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;
//}

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;

    // check if graph has only one vertex
    std::vector<size_t> adj = adjVertices(m, v, size, visited);
    if (adj.empty())
        return dist;
    else
        ++dist;

    // BFS Remix
    std::queue<size_t> stack;
    for (auto&& i : adj) {
        visited[i] = true;
        stack.push(i);
    }

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

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

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