ABC 292 E — Transitivity

考察

操作は到達可能性を変えず、停止時には元グラフで到達可能な全頂点への辺が揃う。最終辺数はΣ_x(|reachable(x)|-1)で、元のM辺を引けば追加回数になる。

採用する候補: 各始点からBFS/DFSで到達数を数える

N,M≤2000なので全始点探索で推移閉包の辺数を求められる。

棄却する候補: 距離2の辺追加を逐次模擬

追加順に依存する再探索が多く、最終状態を直接数える方が明快である。

各xから探索し、x以外の到達頂点数を合計して初期辺数Mを引く。

典型の発動条件

推移閉包

発動条件: 有向辺の推移律を満たすまで追加する。

各始点の到達集合を最終出辺集合とみなす。

問題固有の要素

局所的な距離2追加を繰り返す操作の不変量は到達可能性である。

別の問題へ持ち帰る視点: 反復閉包操作では不変な関係と固定点を先に特定する。

正当性

辺追加u→wがu→v→wから行われるので元の到達性を変えない。操作が止まると二段pathが直接辺を持ち、path長に関する帰納法で全到達pairが直接辺になる。したがって閉包の相異なる頂点pair数から元辺数を引けば追加数が確定する。

実装上の注意

  • 始点自身は辺数へ含めず、初期M辺を最後に一度だけ引く。

復習の核

  • 小グラフで辺追加を停止まで模擬し、閉路・孤立頂点・既に推移的な例と比較する。

計算量と制約

時間

N 頂点、M 辺。全始点探索 O(N(N+M))。

空間

隣接 O(N+M)、visitedとqueue O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 2000; 0 \leq M \leq 2000; 1 \leq u_i ,v_i \leq N; u_i \neq v_i; (u_i,v_i) \neq (u_j,v_j) if i \neq j.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Transitivity の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 推移閉包

主題
  • 推移閉包: 各始点探索または中継許可集合の段階不変条件を保つWarshall更新で推移閉包を求め、必要なら初回到達段階も記録できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 推移閉包

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 推移閉包

      • 各始点探索または中継許可集合の段階不変条件を保つWarshall更新で推移閉包を求め、必要なら初回到達段階も記録できる。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題