何の話かと言うと
要素をグループ分けする問題で、よく Union-Find がテクニックとして取り上げられますが、もうちょっと単純に、同じグループの要素に双方向リンクを貼っていって、最後に、グラフ探索で同じグループの要素をまとめるという手法で間に合う場合もあります。
例1 : D - Equals
互いに入れ替え可能な位置を同一グループと見なします。その後、「整数 の位置
が位置
と同じグループに入っている」という条件を満たす
の個数を数えればOKです。双方向リンクとグラフ探索による実装はこちら。
例2 : D - KAIBUNsyo
数列に現れる数字をノードとして、ペアになる数字を同じグループに属するものとします。それぞれのグループについて「ノード数 - 1」を計算して、これらを合計したものが答えになります。双方向リンクとグラフ探索による実装はこちら。
Union-Find でないと間に合わない例
とは言え、同一グループの探索が何度も走る問題では、Union-Find でないと間に合いません。例えばこちら。
グラフ探索による結果
Union-Find による結果
