Wychodząc z algorytmu O (n)

Question

Tutaj jest problem do rozwiązania:

N Krasnoludy m oświadczenia o który jest wyższy od tego, kto (np Jason < Tim Burton < Jason itp.), Ale niektóre krasnoludy mogą kłamać o zamówieniu i przekazać nam błędne oświadczenie, więc naszym zadaniem jest sprawdzenie, czy możliwe jest zamówienie krasnoludów odpowiednio do ich wielkości. Rezultatem jest albo "Możliwe" albo "Niemożliwe" na wypadek, gdyby karzeł skłamał.

Do tej pory rozumiem pomysł wyobrażenia ukierunkowanego wykresu krasnoludów (z klasą dla krasnoluda), który powinien nam podać nazwę samego krasnoluda i imiona krasnoludów, którzy są od niego wyżsi. Ponieważ powinno to być drzewo opinające, wynik powinien być "Niemożliwy", jeśli wykres zawiera cykl.

Jak mogę to zrobić w środowisku wykonawczym O (n)? Już wypróbowałem niektóre rzeczy z dużą ilością pętli for i pętli rekurencyjnych, ale to albo nie byłoby odpowiednie, albo zajmowanie zbyt dużej ilości czasu podczas obsługi dużej wielkości tego problemu. Później powiedziano mi, aby raczej wymyślić algorytm z O (n) runtime.

Chciałbym wiedzieć, jak powinienem zmienić sposób myślenia, kiedy mam rozwiązać problem w określonym środowisku uruchomieniowym.

Answer 1

Masz rację, używając Grafu ukierunkowanego, ponieważ jest to problem o numerze Topological Sort. Kluczową kwestią jest to, że możesz uzyskać liczbę węzłów początkowych zamiast jednego punktu początkowego. Dlatego nawet jeśli chcesz uzyskać złożoność czasu, będziesz potrzebować również przestrzeni O(n + m).

Łącze wspomina o algorytmie Kahna, który może wykrywać cykle. Wykrywanie cyklu można przeprowadzić za pomocą prostego przejścia systemu plików DFS, o którym wspomniano w tym samym łączu. Jest to również algorytm O(n + m).

Answer 2

Można zrobić DFS skanowanie i sprawdzić, czy krawędź powrotem istnieje (więcej szczegółów here)