Coming up with an algorithm in O(n)

Question

Here is the problem to solve:

N dwarves make m statements about who is taller than who (for example: Jason < Tim, Burton < Jason etc.), but some dwarves could lie about the order and give us the wrong statement, so its our job to check if it's possible to order the dwarves by their size accordingly. The result is either "Possible" or "Impossible" in case a dwarf lied.

So far I understand the idea of imagining a directed graph of the dwarves (with a class for the dwarf) which should tells us the name of the dwarf himself and the names of the dwarves who are taller than him. Since this is supposed to be a spanning tree, the result should be "Impossible" if the graph contains a cycle.

How can I manage this in O(n) runtime? I already tried some stuff with a lot of for-loop and recursion, but that would either not be suitable or take too much time when handling a large-sized case of this problem. I was later told to rather figure out an algorithm with O(n) runtime.

I would like to know how I should change my way of thinking when I am supposed to solve a problem in a certain runtime.

Answer 1

You are right in using a Directed Graph as this is a Topological Sort problem. The key point is that you may get a number of start nodes rather than one single starting point. Hence even if you want O(n + m) time complexity, you will also need O(n + m) space.

The link mentions a Kahn's algorithm which can detect cycles. Cycle detection can be performed using a simple DFS traversal as mentioned in the same link. That is also an O(n + m) algorithm.