これは宿題の質問ではないことに注意してください。私は Kattis のトレーニングを行っており、Union-Find パラダイムの使用を必要とする質問にたどり着きました。問題の性質を考慮して、独自の UnionFind データ構造を実装することにしました。DS のインターフェースが以下をサポートする必要があることを理解しています。
- メイクセット
- find(elem) -> そのセットの代表への参照を返します
- merge(firstElem, secondElem) -> そのセットの 2 つの親をマージします (バランスが取れていることも確認します)
問題は、インデックスが値であり、セットの代表が常にそのインデックスの値である配列を使用して通常実装される整数をサポートするために、このデータ構造を実装していないことです。代わりに、セットに文字列が含まれており、データ構造を選択するのが難しいと感じています。