オイラーパス、アレンジワード

Question

各ドアには多数の磁性プレートがあります。すべてのプレートには1つの単語が書かれています。プレートは、すべての単語が前の単語が終わるのと同じ文字で始まるような順序で配置する必要があります。たとえば、acm "という語の後に" "というモトローラという語を続けることができます。

例： skenzo logicboxes orderbox

ANS：私はこの問題はオイラー路に関連している知っている可能

を注文します。しかし、私はそれを実装することができません。誰かがそれをどのように実装できるか教えてもらえますか？どのようにグラフを作成し、どのノードを接続する必要があるかを意味します。私は隣接行列を使わなければならないが、どのノードを接続しなければならないのか知っている。

Answer 1

私は正しく覚えています。他の人とは違って、あなたが望むのはオイラーの道であり、ハミルトニアンではないということに同意します。結果のグラフでは、単語は頂点の端（最初の文字から最後まで）と文字（ASCIIでは 'a'から 'z'までの小文字の文字のみ）です。

実際には、あなたが望むのはパスそのものではなく、存在するかどうかを知りたいだけです。したがって、グラフ上にオイラーパスが存在するために必要かつ十分な条件が必要です。

明らかに、このようなパスが存在するためには、グラフを接続する必要があります。 ユニオンで効率的にそれを見つけることができますを見つける。
このようなパスが存在すると、頂点の内外の条件が課されます。これらの条件を正しく定式化すれば、a）必要十分な、b）確認が容易です。

自分で条件を見つけるのは楽しいですが、オイラーパスについてはウィキペディアの記事で見つけることもできます。

Answer 2

最初のシンボルと最後のシンボルのASCIIコードをグラフの頂点として使用できます。頂点の順序付けにDFSを使用し、すべての頂点が順序付けされているかどうかを確認することができます。そうであれば、すべての言葉よりもその順序で並べることができます。