プロンプトとコンテキスト
n 人のユーザーと、q 個のタイムスタンプ付き操作が与えられます。add id u v はID付きの無向関係を追加し、remove id はそれを削除し、ask u v はその時点で2人のユーザーが連結しているかを問い合わせます。各関係の追加および削除は最大1回であり、回答を生成する前にすべての操作が既知であるとします。
すべての ask に対して真偽値の回答を返してください。通常の素集合データ構造（DSU）が削除を安全に処理できない理由、関係の生存期間をタイムライン上にマッピングする方法、状態を復元する方法、および考慮すべき境界条件と計算量について説明してください。対象はオフライン動的連結性であり、任意のオンライン更新ではありません。
面接官が見ているポイント
- 辺が消失した際に、通常のUnion-Findの単調な不変条件が崩れることを認識できているか。
- 各辺を半開区間の生存期間
[add time, remove time)として表現できるか。 - 区間を
O(log q)個のセグメント木ノードに分解できるか。 - 経路圧縮を行わず、サイズによる結合（union by size）を用いたロールバックDSUを実装できるか。
- スナップショット、再帰の復帰、クエリの正当性を関連付けて説明できるか。
最初に明確にすべき質問
- すべての操作は事前に分かっていますか？オンラインで回答する必要がある場合、タイムラインを用いたアプローチは適用できません。
- すべての関係に一意のIDがありますか？一意のIDがない場合、重複する辺の削除が曖昧になります。
- グラフは無向ですか？有向グラフの場合は、異なる到達可能性の構造が必要です。
- 削除された後に同じIDが再度追加されることはありますか？その場合、各生存期間に個別の区間が必要です。
- クエリは連結性のみですか、それとも連結成分のサイズ、最短経路、実際の経路も含まれますか？
30秒の回答フレームワーク
通常のDSUは連結成分をマージできますが、どの構造を分割すべきか分からないため辺を削除できません。操作を走査して各辺に対して [add, remove) を作成し、削除のない辺は q まで延長します。各区間を時間軸上のセグメント木に配置します。DFS中にノードの辺を適用し、葉でクエリに回答し、ノードから抜ける際に進入時のスナップショットにロールバックします。ロールバックDSUでは経路圧縮を避け、サイズによる結合を使用するため、各変更が記録され、全体の計算量は O(q log q log n) 時間、O(n + q log q) 空間となります。
ステップごとの詳細解説
ステップ1：通常のDSUが失敗する理由を特定する
通常のDSUは、これまでに行われたすべてのマージ結果を保持します。1つの辺を削除すると、別の辺を経由して連結成分が維持される場合もあれば、木を分割する必要がある場合もあります。親ポインタだけでは影響を受けるカットを特定できません。安全な「逆マージ」は存在しません。
ステップ2：辺の生存期間区間を構築する
各 add の時刻を記録します。その remove が現れたら、[add, remove) を閉じます。半開区間の形式により、削除タイムスタンプの時点で辺が存在しないようにします。最後まで開いたままの辺は [add, q) になります。
ステップ3：セグメント木で区間をカバーする
区間を完全にカバーするセグメント木ノードに格納します。1つの区間は最大 O(log q) 個のノードを占有します。ノードに格納されたすべての辺は、そのノードの時間範囲全体で有効であるため、各葉ごとではなく1回だけマージされます。
ステップ4：ロールバックDSUを設計する
parent と size を保持します。find は経路圧縮を行わずに親を辿ります。union は小さい方の根を大きい方の根に結合し、変更された子、根、および古いサイズを履歴スタックにプッシュします。サイズによる結合により、木の高さは O(log n) に抑えられます。
ステップ5：スナップショットと復元を用いたDFS
進入時に履歴の長さを保存し、ノードの辺を適用し、葉で ask に回答します。両方の子の処理が完了したら、保存された長さまでポップして復元します。親ノードの辺は次の子に対しても有効なままですが、子の辺が兄弟ノードに漏れることはありません。
ステップ6：実装の構造
実装は4つのフェーズで構成されます。半開区間の構築、時間セグメント木への各区間の追加、ロールバックDSUによる走査、および葉での回答です。重要な詳細は、経路圧縮を行わないこと、古い連結成分サイズを記録すること、そしてスナップショットへ正確に復元することです。
ステップ7：不変条件と計算量の証明
セグメント木ノードへの進入時、DSUにはそのノードの範囲全体でアクティブな辺と、祖先によって適用された辺のみが正確に含まれます。子ノードの辺はその部分木内にのみ存在し、復帰時に削除されるため、葉はアクティブな辺の結合状態を正確に参照します。各辺は O(log q) 個のノードに格納され、サイズによる結合を用いた各マージのコストは O(log n) であるため、計算量は O(q log q log n) 時間、O(n + q log q) 空間となります。
ステップ8：代替案と失敗ケースの比較
辺の追加と連結性のクエリのみであれば、通常のDSUの方がシンプルであり、均し計算量はほぼ定数時間です。真のオンライン削除には動的連結性データ構造が必要であり、タイムラインツリーでは未知の未来の削除を知ることはできません。また、DSUは最短経路には対応できないため、BFS、ダイクストラ法、または別の経路構造が必要です。
質の高い模範解答
まず、すべての操作が既知であり、すべての関係に安定したIDがあることを確認します。通常のDSUはマージのみを行い、削除によって連結成分の不変条件が壊れるため、操作を走査して半開区間の辺の生存期間を作成し、未オープンの辺を最後まで延長します。これらの区間を時間セグメント木に配置し、DFS中にノードの辺をマージし、葉で連結性に回答し、復帰時に進入時の履歴の長さにロールバックします。ロールバックDSUは経路圧縮を避け、サイズによる結合を使用し、親とサイズの変更を記録することで木の高さを O(log n) に抑えます。各辺は O(log q) 個のノードに現れるため、時間計算量は O(q log q log n)、空間計算量は O(n + q log q) です。追加のみの場合は通常のDSUを使用し、オンライン削除や最短経路の場合はより強力な動的構造を選択します。
よくあるミス
- 削除のためにマージを逆操作しようとする → マージは可逆ではない → 生存期間区間とロールバックを使用する。
- ロールバックDSUで経路圧縮を使用する → 親の書き換えが多くログに記録されない → 圧縮なしのサイズによる結合を使用する。
- 生存期間を閉区間
[add, remove]として扱う → 削除時点でも辺が有効になってしまう →[add, remove)を使用する。 - すべての葉ですべての辺を再マージする → セグメント木の計算量の利点が失われる → カバーするノードでマージする。
- 親ポインタのみを復元する → その後のサイズによる結合の選択が破損する → 古いサイズも復元する。
- オンライン更新に対してオフライン手法を提案してしまう → 未来の区間が不明 → まず対話モデルを確認する。
フォローアップ質問と回答
削除後に同じ関係IDが再度追加された場合はどうなりますか？
add ごとに新しいオープンレコードを作成し、remove は現在オープンになっている生存期間のみを閉じるようにします。これにより、同じIDでも古いレコードを上書きせず、複数の互いに素な区間が生成されます。
同じ設計で現在の連結成分のサイズに回答できますか？
はい。根の size を保持し、find から根を返し、ロールバック中に古いサイズを復元します。追加の連結成分の集約値も、履歴スタックに古い値を保持し、可逆な更新を行う必要があります。
q が非常に大きく、再帰やメモリがボトルネックになる場合はどうしますか？
まず O(q log q) の区間ストレージが収まるか確認します。その後、再帰的DFSを明示的なスタックに置き換えるか、辺のストレージをコンパクトにするか、時間ブロックごとに処理します。ロールバックの正当性を損なうため、経路圧縮を有効にしてはいけません。
なぜタイムライン手法をそのままオンライン削除に変更できないのですか？
この手法は、各区間を構築するために削除タイムスタンプを必要とします。オンライン入力では未来のタイムスタンプが分からないため、前処理で木に辺を配置できません。オンライン動的連結性のために設計されたデータ構造を使用し、そのレイテンシと実装コストを再評価してください。