Venir avec un algorithme en O (n)

Question

Voici le problème à résoudre:

N Nains font m des déclarations au sujet qui est plus grand que qui (par exemple: Jason < Tim Burton < Jason etc.), mais certains nains pourraient mentir à propos de l'ordre et nous donner une fausse déclaration, donc c'est notre travail de vérifier s'il est possible de commander les nains en fonction de leur taille. Le résultat est soit "Possible" soit "Impossible" au cas où un nain aurait menti. Jusqu'ici je comprends l'idée d'imaginer un graphe orienté des nains (avec une classe pour le nain) qui devrait nous indiquer le nom du nain lui-même et les noms des nains qui sont plus grands que lui. Puisque ceci est censé être un arbre couvrant, le résultat devrait être "Impossible" si le graphique contient un cycle. Comment puis-je gérer ceci dans O (n) runtime?

J'ai déjà essayé quelques trucs avec beaucoup de for-loop et de récursion, mais cela ne serait pas approprié ou prendrait trop de temps lors de la manipulation d'un cas de grande taille de ce problème. On m'a dit plus tard de trouver un algorithme avec O (n) runtime.

Je voudrais savoir comment je devrais changer ma façon de penser quand je suis censé résoudre un problème dans un certain temps d'exécution.

Answer 1

Vous avez raison d'utiliser un graphique dirigé car il s'agit d'un problème Topological Sort. Le point clé est que vous pouvez obtenir un certain nombre de nœuds de départ plutôt qu'un seul point de départ. Par conséquent, même si vous voulez O(n + m) complexité de temps, vous aurez également besoin d'espace O(n + m).

Le lien mentionne un algorithme de Kahn qui peut détecter des cycles. La détection de cycle peut être effectuée en utilisant une simple traversée DFS comme mentionné dans le même lien. C'est aussi un algorithme O(n + m).

Answer 2

Vous pouvez faire un scan DFS et vérifier si un bord arrière existe (plus de détails) here