がOでアルゴリズムを考え出す（N）ここ

Question

は解決する問題である。

Nドワーフがより背が高い人約メートル文を作る人 （例：ジェイソン<ティム、バートン<ジェイソンなど）、ドワーフの中には秩序について嘘をついて、間違った声明を出すことがあるので、ドワーフのサイズを適切に並べることができるかどうかを確認する仕事です。矮星が嘘をついた場合の結果は、 "可能"または "不可能"のいずれかです。

これまで私は、ドワーフ自身の名前と彼よりも背の高いドワーフの名前を教えてくれるドワーフ（矮星のクラスを持つ）の有向グラフを想像するという考えを理解しています。これはスパニングツリーであると考えられるので、グラフにサイクルが含まれている場合、結果は "不可能"になります。

これをO（n）ランタイムでどのように管理できますか？私はすでに多くのfor-loopとrecursionを使っていくつかのものを試しましたが、この問題の大規模なケースを処理するには適切でないか、あまり時間がかかるでしょう。私は後で、O（n）ランタイムでアルゴリズムを理解するように言われました。

特定のランタイムで問題を解決する必要があるときに、自分の考え方をどのように変えるべきかを知りたいと思います。

Answer 1

これはTopological Sortという問題があるため、あなたは指向グラフを使用しています。要点は、単一の開始点ではなく、いくつかの開始ノードを取得できることです。したがって、O(n + m)時間の複雑さが必要な場合でも、O(n + m)スペースが必要です。

リンクには、サイクルを検出できるKahnのアルゴリズムが記載されています。サイクル検出は、同じリンクで言及されている単純なDFSトラバーサルを使用して実行できます。それはO(n + m)アルゴリズムでもあります。

Answer 2

あなたは、私は答えとして、Javaコードまたは結果のいずれかの種類を望んでいないが、いくつかは、私が管理できるのに役立ちますDFSスキャンを実行し、バックエッジが