Codingame Solution: Dwarfs standing on the shoulders of giants

Solution

We need some way to store the graph. I decided to store the graph as key-value mapping, with the key the number of the node and the value an array of all adjacent nodes. In the first step we duplicate in a path and a root mapping:

var path = {};
var root = {};

var n = readline();

for (var i = 0; i < n; i++) {

    var t = readline().split(" ");

    if (undefined === path[t[0]]) {
        path[t[0]] = [t[1]];
        root[t[0]] = [t[1]];
    } else {
        path[t[0]].push(t[1]);
        root[t[0]].push(t[1]);
    }
}

In the next step, we go over all nodes in the root mapping and delete every node from it, which occurs as a node. The idea is that only the real root nodes will remain in root:

for (var i in root) {
    for (var j = 0; j < root[i].length; j++) {
        delete root[root[i][j]];
    }
}

The only remaining thing left is looping over all root nodes and find the maximum diameter of the graph:

var s = 0;
for (var i in root) {
    s = Math.max(s, diameter(path, i));
}
print(s);

The only missing piece is the diameter calculation. Let's define this recursively. If a node does not have a certain element, the recursion needs to end. Otherwise we loop in a depth-first-search manner over all adjacent elements. The maximum depth we can find this way is the depth of the current node. But hold on. When we calculate the depth this way, a lot of nodes will be computed over and over again, when they're visited via another node. Introducing a memory which stores nodes we've already seen can help here. The diameter implementation then looks like this:

var hash = {};
function diameter(path, node) {

    if (!path[node]) {
        return 1;
    }

    if (hash[node]) {
        return hash[node];
    }

    var max_d = 0;
    for (var i = 0; i < path[node].length; i++) {
        max_d = Math.max(max_d, diameter(path, path[node][i]));
    }
    return hash[node] = 1 + max_d;
}