2015年2月7日土曜日

AOJ 0225

Kobutanukitsuneko

問題:
n個の文字列が与えられたときにそのn個全部を使ってしりとりのループを作ることが出来るかどうかを判定する問題。

解法:
アルファベットをノード、単語をエッジと見て各単語の最初と最後の文字のアルファベットノードに有向枝をはったグラフを作り
・グラフが連結かどうか
・オイラーグラフかどうか

を判定すれば良い

0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...