ABC 266 F — Well-defined Path Queries on a Namori

考察

連結N頂点N辺の無向グラフは閉路をちょうど一つ持ち、その各閉路頂点へ木が付いたなもりグラフである。同じ閉路頂点に付く木の中の二頂点間は一意pathだが、異なる閉路根に属すれば閉路を回る二方向がある。leaf pruning後に残る2-coreはこのグラフでは唯一のcycleそのものである。

棄却する候補: 各queryで一方からDFSし、単純pathを二本以上見つけるまで探索する。

Q回の全グラフ探索は大きく、単純path列挙自体も不要である。

採用する候補: 次数1頂点を反復削除してcycle頂点を抽出し、各cycle頂点からcycle辺を越えない探索で全頂点へ根labelを付ける。

queryの一意性は二頂点の所属cycle根labelが等しいかだけで判定できる。

典型の発動条件

次数1除去によるcycle抽出

発動条件: 連結unicyclic graphの唯一cycle上の頂点を求めたいとき。

degree 1をqueueへ入れ、削除に伴い新たにdegree 1になった頂点を反復処理する。

core頂点を根とする成分labeling

発動条件: cycleやcoreの各頂点に木が付いた構造で、どの根へ属すかを多数照会するとき。

各core頂点を異なるsourceとして、core間辺を使わずDFS/BFSしてroot labelを配る。

問題固有の要素

cycle上の頂点自身も自分を根labelとして持つため、cycle頂点とその付属木の頂点のqueryも同じ等値判定で扱える。

別の問題へ持ち帰る視点: core+branches分解ではcore要素も各branch componentの代表として含めると境界caseを統一できる。

正当性

一意cycleを除く枝は木でcycle根へ唯一のpathを持つ。同じ根の木内はunique path、異なる根間はcycle両方向の二path。cycle頂点を別rootとして枝全体へラベルを伝えると一致判定が必要十分。

実装上の注意

  • pruningでは現在degreeを減らし、queueから除かれなかった頂点をcycle flagとして残す。
  • label探索では隣接する別cycle頂点へ進まず、各非cycle頂点を一度だけ訪問する。

復習の核

  • N頂点N辺の連結グラフを見たら、唯一cycleと付属木へ分解してqueryの本質を探す。
  • path本数を直接数えず、cycleへ入るrootが同じかどうかで代替できないか確認する。

計算量と制約

時間

N 頂点N辺、Q質問。leaf peelingとrootラベル O(N)、各質問 O(1)。

空間

木付きcyclegraph、ラベル O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 2 \times 10^5; 1 \leq u_i < v_i\leq N; (u_i,v_i) \neq (u_j,v_j) if i \neq j.; G is a connected simple undirected graph with N vertices and N edges.; 1 \leq Q \leq 2 \times 10^5; 1 \leq x_i < y_i\leq N; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Well-defined Path Queries on a Namori の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単一サイクル成分とgraph core

主題
  • 単一サイクル成分とgraph core: 連結成分のE−V+1から独立な閉路数を判定し、E=Vなら唯一のcycleを持つことを示せる。必要なら次数1以下の頂点を反復削除し、残るcoreと削除順を求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 単一サイクル成分とgraph core

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

      学習の位置

      体系上の位置: 単一サイクル成分とgraph core

      • 連結成分のE−V+1から独立な閉路数を判定し、E=Vなら唯一のcycleを持つことを示せる。必要なら次数1以下の頂点を反復削除し、残るcoreと削除順を求められる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題