Can you believe we didn’t think of that problem name until 2017?
For a server s to be hacked:
In the easy subproblem, we can use DFS or BFS to check all conditions directly for every server. E.g. to check condition 4, we can literally temporarily remove s from the graph and see if a DFS from 1 visits n. This is also useful for checking that your hard solution didn’t miss any special cases.
In the hard subproblem, we need something faster.
First, we filter out all servers that aren’t reachable from 1 or that can’t reach n. This takes care of conditions 1 and 2, and makes sure that the other servers won’t cause false positives for condition 4.
Then, we find the strongly connected components and a topological sort of the directed acyclic graph formed by them. Tarjan’s algorithm can do both together.
For a server to fulfill condition 3, it must be the only server in its strongly connected component, and it also can’t have a self-loop (s, s).
The final condition can be checked by looking at the directed acyclic graph and walking through the topological sort from 1 to n. (Recall that we removed all servers that can’t be reached from 1 or that can’t reach n.) During this, we remember the farthest edge we’ve seen so far. If there is an edge that starts from somewhere before the current vertex, and ends somewhere after the current vertex, then it’s possible to use it to skip over this vertex and so it doesn’t meet condition 4. If all edges from previous vertexes end in the current vertex or earlier, then it fulfills the condition.