Codeforces #396 Div. 2 D: Mahmoud and a Dictionary
等しい要素は、素集合データ構造でくっつけていく。
また、互いに素なAとBが反意語であることを示すのに
an[A] = Bかつan[B] = A
のような配列を使う。(unifon find木の各集合を代表する頂点を使えば単なる配列になる。)
あとは問題文に従ってこれらを操作するだけだが、矛盾する場合のチェックはすこし分かりづらかった。以下のとおり。
等しい要素は、素集合データ構造でくっつけていく。
また、互いに素なAとBが反意語であることを示すのに
an[A] = Bかつan[B] = A
のような配列を使う。(unifon find木の各集合を代表する頂点を使えば単なる配列になる。)
あとは問題文に従ってこれらを操作するだけだが、矛盾する場合のチェックはすこし分かりづらかった。以下のとおり。