考察
連結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.
出典