CODE FESTIVAL 2016 Final C - Interpretation
解法
ある人とある人の間に辺が貼ってあるか、ある人とある人が連結であることがわかればよい。ここで、UnionFindを使いたい気持ちになるので、どうにか使えないか考える。
ここでは、問題の入力例1を元に考えることにする。
この図を縦に見ると、ノードが同じ言語に並んでいる場合は、一つ目の条件である「2人ともが話すことの出来る言語が存在する」を満たしている。
また、１人目が３人目とコミュニケーションを取るためには、２人目を経由する必要があるが、これは図で表すと次のようになる。
赤色の矢印の両端の人はコミュニケーションができる。水色の矢印の両端はが話せる言語である。
この時、AとBがを経由してコミュニケーションを取ることができる時、AとBにパスが存在する。
水色の矢印については、同じ人がコミュニケーションを取ることができるとみなせるので、統合する必要はない（自己ループは考えない）。
赤色の矢印については、両端の人でコミュニケーションを取ることができるので、両端の人を統合し、一つのグループを作る。
あとは、人の参加者が同じグループに入っているかを調べれば、全ての参加者とコミュニケーションを取ることができるかを調べられるので、この問題が解ける。
おわりに
UnionFindの練習にはちょうどいいかも。
