ABC097 D - Equals

問題
提出コード

解法

と、およびとが交換可能な場合、とは2回の操作で交換可能になります。
このようなことが全てのペアについて言えるので、結局は

• 入力で与えられるを辺とみなして頂点辺のグラフを作成したときに、最終的に連結な頂点同士はスワップ可能

となります。
あとは、任意のについて、とがスワップ可能かどうかを調べ、可能な個数を求めれば答えとなります。
連結な部分の判定は、Union-Find木を用いれば用意に判定できるので、それを利用すればよいです。

解法

コンテスト当時は、初めてUnion-Find木に触れた問題なので、とても記憶に残っています。実装もUnion-Findは優しめなので結構教育的な一問？だと思っています。