壊れたアクセサリー [yukicoder No.517]

前提知識

トポロジカルソート

解説

http://yukicoder.me/submissions/175908

各断片について、隣接している文字に有向辺が張られていると考える。
例えば、ABCでは「A->B, B->C」と辺を張る。
これで両者の断片について辺を貼ったあと、トポロジカルソートをする。

これで閉路判定もできるので、閉路があれば、隣接関係がループしてしまうので、"-1"を出力して終わり。
答えはトポロジカルソート順で確定していけばいい。

これでほぼ答えが求まるが、チェックする必要がある。
これでは、AB + CDとCD + ABの二通りがあって確定できない場合が考えられてない。
答えの隣接している文字に有向辺があるかをチェックして、だめなら"-1"