Aim Tech Div2 C. Graph and String
本番中は，UnionFindのコードをコピペして座ってるだけ．
本番後，Twitterで参加者のツイートを見てAC．
問題概要
- a,b,cから構成される文字列に対応したグラフを考える
- 文字列のi番目の文字はi番目のノードに対応している
- 文字列のi番目の文字とj番目の文字が同じであればノードi, jは必ず隣接する
- i番目の文字とj番目の文字がアルファベット順で隣同士であれば隣接する
- すなわち，aとb，bとcは隣接する
- aとcは隣接しない
- グラフが与えられるので以上の条件を満たす文字列があるかを考える
- 無い場合は“No”，ある場合は“Yes”と候補として考えられる文字列を一つ出力する
解法
- 全てのノードからbの候補となるもの見つける
- bは全てのノードと隣接している
- すなわちbから出る辺はn-1本
- bの候補とそのエッジを取り除いたグラフから強連結成分を見つける
- 色々あるけど張ってあったのでUnionFindを使った
- 検出した強連結成分はaとcの候補
- 3つ以上強連結成分があればNoを出力
- 検出した強連結成分は完全グラフでなければならない
- bの候補に向かって張ってる辺を除いた辺の数が強連結成分のノード数-1となる
- なっていなければNoを出力
- ここまででNoが出力されていなければYes
- b候補のノードをb，強連結成分に属するノードをaかc (異なる強連結成分同士で異なればどちらでもよい) として出力
