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

const std::vector<size_t> maxDist(const std::vector<std::vector<size_t>>&);
size_t maxDistUtil(const std::vector<std::vector<size_t>>&, const size_t&);
size_t maxVal(const std::vector<size_t>&);


int main() {
    constexpr size_t n = 4;
    std::vector<std::vector<size_t>> graph(n);
    graph[0] = { 1, 2 };
    graph[1] = { 3 };
    graph[2] = { 1, 3 };

    const std::vector<size_t>& resultM = maxDist(graph);
    for (size_t i = 0; i < resultM.size(); ++i)
        std::cout << i << ": " << resultM[i] << std::endl;

    system("pause");
    return 0;
}

const std::vector<size_t> maxDist(const std::vector<std::vector<size_t>>& graph) {
    const size_t& n = graph.size();
    std::vector<size_t> res(n);
    for (size_t i = 0; i < n; ++i)
        res[i] = maxDistUtil(graph, i);
    return res;
}

size_t maxDistUtil(const std::vector<std::vector<size_t>>& graph, const size_t& s) {
    const size_t& n = graph.size();
    std::vector<size_t> d(n, UINT_MAX);
    d[s] = 0;
    std::set<std::pair<size_t, size_t>> q; // dist, number of vertex
    q.insert(std::make_pair(d[s], s));
    while (!q.empty()) {
        size_t v = q.begin()->second;
        q.erase(q.begin());

        for (size_t j = 0; j < graph[v].size(); ++j) {
            size_t to = graph[v][j];
            if (d[v] + 1 < d[to]) {
                q.erase(std::make_pair(d[to], to));
                d[to] = d[v] + 1;
                q.insert(std::make_pair(d[to], to));
            }
        }
    }
    return maxVal(d);
}

size_t maxVal(const std::vector<size_t>& d) {
    size_t max = 0;
    for (const size_t& i : d)
        if (i < d.size() && i > max)
            max = i;
    return max;
}