The Goal
Rules
We choose to represent each person by a distinct integer. If person #1 has influenced persons #2 and #3 and person #3 has influenced #4 then there is a succession of thoughts between #1, #3 and #4. In this case, it’s the longest succession and the expected result will be 3, since it involves 3 people.
If we were to complete this example when we learn that person #2also influenced persons #4 and #5, then the longest succession will still have a length of 3, but there will now be several of them.
If we now add that person #10 influenced person #11, the result remains 3. However, as soon as we learn that #10 also influenced #1and #3, then the result becomes 4, since there is now a succession involving 4 people, which is #10, #1, #2, #5.
Note: It takes time for a thought to influence others. So, we will suppose that it is not possible to have a mutual influence between people, i.e. If A influences B (even indirectly through other people), then B will not influence A (even indirectly). Also, you can not influence yourself.
Game Input
Line 1: The number N of relationships of influence.
N following lines: a relationship of influence between two people in the form of X (whitespace) Y, which indicates that X influences Y. The relationships of influence are listed in any order.
0 < X, Y < 10000
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;
}