前置き
グラフから頂点を除くとき、それに隣接する辺は自動的に除かれるものとします。
改題
原作：https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day2/problems/J
コンテスト：https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day2/info
問題 $(1)$
$N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられる。 $3 \leq N$ が成り立つ。頂点には $0$ から $N-1$ の番号を振る。便宜上、頂点 $0$ を $s$ 、頂点 $N-1$ を $t$ と呼ぶ。 $x=1,2,3,\cdots ,N-2$ のそれぞれについて、以下の条件をすべて満たすような $y$ を数え上げよ。
- $y$ は $1$ 以上 $N-2$ 以下の整数である。
- $y \ne x$
- $G$ から $2$ 頂点 $x,y$ を除いたグラフにおいて、 $s,t$ は連結でない。
定理 $1$
問題 $(1)$ を $O(N+M)$ 時間で解ける。
利用する典型アルゴリズム
- 基本的なフローアルゴリズム
- block-cut tree ・ biconnected なグラフの性質
- 深さ優先探索
- 累積 $\min$ / $\max$
解説
自明な場合
補題 $1.1$
頂点 $0$ と頂点 $N-1$ が連結である場合の問題 $(1)$ $\cdots$ 問題 $(1.1)$ を $O(N+M)$ 時間で解けるならば、 定理 $1$ が導かれる。
補題 $1.1$ 証明
頂点 $0$ と頂点 $N-1$ が連結かどうかは深さ優先探索で判定できる。連結でない場合は、 $x$ にかかわらず $0,x,N-1$ 以外の頂点を数え上げるため、 答えは $N-3$ である。(証明終)
補題 $1.2$
頂点 $p$ を除いたときに、頂点 $0$ と頂点 $N-1$ が連結でなくなるような $p$ の集合を $\mathrm{A_{rt}}$ とする。問題 $1.1$ の $x\notin\mathrm{A_{rt}}$ かつ $y\notin\mathrm{A_{rt}}$ の部分のみを考える場合 $\cdots$ 問題 $(1.2)$ を $O(N+M)$ 時間で解けるならば、 定理 $1$ が導かれる。
補題 $1.2$ 証明
$\mathrm{A_{rt}}$ は block-cut tree から求まる。
$x\in\mathrm{A_{rt}}$ ならば、すべての頂点を数え上げるので答えは $N-3$ である。
$x\notin\mathrm{A_{rt}}$ ならば、 $y\in\mathrm{A_{rt}}$ は条件を満たすので、問題 $(1.1)$ での答えは問題 $(1.2)$ での答えに $\mathrm{A_{rt}}$ の要素数を足したものである。(証明終)
biconnected components に分解
補題 $2.1$
$G$ が bicennected （二点連結）である場合の問題 $(1)$ $\cdots$ 問題 $(2.1)$ を $O(N+M)$ 時間で解けるならば、 定理 $1$ が導かれる。
補題 $2.1$ 証明
block-cut tree を用いて、問題 $(1)$ の各 biconnected components について、含まれる頂点集合と辺集合を $O(N+M)$ 時間で求められる。
頂点 $p$ を、 block-cut tree における $s-t$ 単純パスに含まれない biconnected components にしか含まれない頂点とする。 block-cut tree の性質から、頂点 $p$ を通る $s-t$ 単純パスは存在しない。よって、ある頂点に加えて $p$ を削除してもしなくても $s,t$ の連結性に変化はない。従って、問題 $(1.2)$ について、頂点 $p$ を除いても求める値は変わらない。
block-cut tree は次のようなパスと見なせるものになる。
$$s-(\text{block})-(\text{articulation})-\cdots -(\text{articulation})-(\text{block})-t$$
実際は $s,t$ は隣接する block に含まれる。
$x$ または $y$ が $(\text{articulation})$ である場合は問題 $(1.2)$ では排除されている。異なる $(\text{block})$ からそれぞれ $1$ 頂点除く場合は、 biconnected の性質から $s,t$ が連結になり、数え上げられない。従って、 $1$ つの $(\text{block})$ から $2$ 頂点を除く場合のみ数え上げればよい。
$(\text{articulation})-(\text{block})-(\text{articulation})$ の部分について考えるとき、 $(s)-(\text{block})-(t)$ と置き換えれば問題 $(1.2)$ のうち $G$ が biconnected な場合に帰着される。
従って、問題 $(2.1)$ が解けると問題 $(1.2)$ も解け、前の補題により問題 $(1)$ も解ける。(証明終)
点素な $2$ つのパス
補題 $3.1$
グラフ $G$ が biconnected のとき、両端以外で頂点を共有しない $2$ 個の $s-t$ 単純パスの例を $O(N+M)$ 時間で求められる。
補題 $3.1$ 証明
求める $2$ 個の単純パスの存在はメンガーの定理より明らかである。
頂点流量付きフローを流量 $2$ だけ流せば求まる。(証明終)
パスの省略
(2021年11月22日編集 : (条件 $4\text{A}$,$4\text{B}$ を追加))
以降、便宜上、「パス $A$ に含まれる頂点」を「赤頂点」、「パス $B$ に含まれる頂点」を「青頂点」、「パス $A$ にもパス $B$ にも含まれない頂点」を「灰頂点」と言い換える。 $s,t$ は赤頂点かつ青頂点である。また、「ある灰頂点から、灰頂点のみを通って行き来できるような頂点の集合」を「灰頂点の連結成分」ということにする。
問題 $(2.1)$ のグラフ $G$ について、補題 $3.1$ の条件に従って $2$ つのパス $A,B$ をとったとする。次の条件が満たされる場合の問題 $(1)$ を問題 $(4.1)$ とする。
- 灰頂点の連結成分に隣接する頂点のうち、 $A$ または $B$ に含まれるものの集合を $C_{\text{adj}}$ とする。このとき、任意の $C_{\text{adj}}$ について次の条件はすべて満たされる。
- (条件 $1$ ) $2$ 頂点 $x,y$ が $C_{\text{adj}}$ に含まれ、かつ青頂点ならば、 $x,y$ は互いに隣接している。
- (条件 $2\text{A}$ ) $C_{\text{adj}}$ は赤頂点を含む。
- (条件 $2\text{B}$ ) $C_{\text{adj}}$ は青頂点を含む。
- (条件 $3$ ) $C_{\text{adj}}$ に含まれる $2$ 頂点 $x,y$ がともに赤頂点で、互いに隣接しないならば、 $C_{\text{adj}}$ は $2$ つの青頂点を含む。
- (条件 $4\text{A}$ ) パス $A$ にもパス $B$ にも含まれない辺が結ぶ $2$ 頂点は、赤頂点どうしでない。
- (条件 $4\text{B}$ ) パス $A$ にもパス $B$ にも含まれない辺が結ぶ $2$ 頂点は、青頂点どうしでない。
補題 $4.1$
問題 $(4.1)$ が $O(N+M)$ 時間で解けるならば、定理 $1$ が導かれる。
補題 $4.1$ 証明
パスの性質より、 $A,B$ から $1$ 頂点ずつ除く場合のみ考えれて数え上げてよい。
問題 $(2.1)$ のグラフを次の手順で変形する。 $G_\text{A}$ とする。(2021年12月1日編集)
- $G$ から青頂点のうち $s,t$ 以外を除いて $G_1$ とする。
- $G_1$ で、除くと $s,t$ が非連結になる頂点の集合を block-cut tree から求め、 $s,t$ を加え、 $s$ から $t$ へパス $A$ の順に並べたものを $A’$ とする。
- $A’$ がパスになるように辺を足し、パス $A$ を $A’$ に取り替える。
- $G_1$ に対し、パス $B$ とそれに隣接していた辺を復元したグラフを $G_2$ とする。
- $G_2$ について、灰頂点の連結成分に隣接する青頂点がない場合、そのような灰頂点をすべて取り除く。
手順 3. について、 block-cut tree の性質より、パス $A$ に含まれるべき頂点が抜けることはない。
手順 5. について、 block-cut tree の性質より、仮にこのような灰頂点の連結成分が複数の赤頂点に隣接しているならば、その赤頂点は新しいほうのパス $A$ で隣接する $2$ 頂点である。従って、この手順を行っても必要な頂点や辺が抜けることはない。
この手順を通して、灰頂点の連結成分に赤頂点と青頂点の両方が隣接している場合、その性質は失われないことに注意する。 $\cdots [1]$ また、この時点で $C_{\text{adj}}$ に含まれる $2$ 頂点 $x,y$ がともに赤頂点で、互いに隣接しないことはないことに注意する。 $\cdots [2]$
$G_A$ に対して、手順 1. から 5. を $A,B$ を入れ替えて読んで行う。結果のグラフは $G_{\text{AB}}$ とする。
$[1]$ と手順 5. より、 $G_{\text{AB}}$ で条件を確認すると (条件 $2\text{A}$ ) 、 (条件 $2\text{B}$ )、(条件 $4\text{A}$ )、(条件 $4\text{B}$ ) を満たす。また、手順 3. から (条件 $1$ ) も満たされる。 $[2]$ より、 (条件 $3$ ) の仮定を満たす $C_{\text{adj}}$ は青頂点から生じた灰頂点を含み、パス $B$ 内の位置関係で両側の青頂点に隣接する。従って、 (条件 $3$ ) を満たすことも示される。
以上により、問題 $(2.1)$ を、数え上げる頂点の組 $(x,y)$ を変えることなく問題 $(4.1)$ の条件を満たすように変形できる。 (証明終)
橋渡し部分の省略
（2021年9/30 修正）問題 $(2.1)$ のグラフ $G$ について、補題 $3.1$ の条件に従って $2$ つのパス $A,B$ をとったとする。すべての頂点が $A$ または $B$ に含まれる、パス $A$ にもパス $B$ にも含まれない辺は必ず赤頂点と青頂点を結ぶ場合の問題 $(1)$ を問題 $(5.1)$ とする。
補題 $5.1$
問題 $(5.1)$ が $O(N+M)$ 時間で解けるならば、定理 $1$ が導かれる。
補題 $5.1$ 証明
問題 $(4.1)$ のグラフ $G$ を以下の手順で変形し、問題 $(5.1)$ の条件を満たすようにする。
- 灰頂点をすべて除く。
- 元のグラフで、赤頂点 $a$ と青頂点 $b$ $(a,b,s,t$ は相異なる $)$ がともに、ある灰頂点の連結成分に隣接している場合に限り、またその場合は必ず、新しいグラフの $a,b$ を直接辺で結ぶ。
このグラフが $O(N+M)$ 時間で構築でき、 $O(N)$ 頂点 $O(M)$ 辺の条件を保つことは、問題 $(4.1)$ の (条件 $1$ ) から明らかである。 以下ではこの変形によって数え上げる頂点の組 $(x,y)$ が変わらないことを示す。
変形前の灰頂点の連結成分に隣接する赤頂点と青頂点それぞれの個数で場合分けを行い、変形によって赤青それぞれ高々 $1$ 頂点ずつ除いたときの連結の様子が変化しないことを示す。
- 赤 $1$ 個・青 $1$ 個の場合、赤青両方の頂点が除かれないとき、それらを連結にするという効果が変わらない。
- 赤 $1$ 個・青複数、つまり青 $2$ 個の場合、赤頂点が除かれたときに連結の要素が余るが、 (条件 $1$ ) より、それはすでに隣接している青頂点なので連結の様子は変化しない。
- 赤複数のとき、 (条件 $3$ ) より、青頂点は $2$ 個ある。どちらの青頂点を除いても、あるいは青頂点が除かれなくても、赤頂点の連結の様子に影響しない。
以上により、問題 $(4.1)$ を、数え上げる頂点の組 $(x,y)$ を変えることなく、また問題サイズのオーダーを変えずに、問題 $(5.1)$ の条件を満たすように $O(N+M)$ 時間で変形できる。 (証明終)
簡単な区間の問題
定理 $1$
問題 $(1)$ を $O(N+M)$ 時間で解ける。
定理 $1$ 証明
問題 $(5.1)$ を $O(N+M)$ 時間で解く方法を示す。
数え上げる頂点の組 $(x,y)$ の組の条件を考える。対称性より、 $x$ を赤頂点、 $y$ を青頂点として考える。頂点を
- グループ $S$ ： $x$ より $s$ に近い赤頂点と $y$ より $s$ に近い青頂点
- グループ $T$ ： $x$ より $t$ に近い赤頂点と $y$ より $t$ に近い青頂点
の $2$ つのグループに分ける。 $x,y$ を除いたあとに $s,t$ が非連結であるための必要十分条件が
- グループ $S$ の頂点とグループ $T$ の頂点を結ぶ辺が存在しない。 $\cdots[1]$
であることは明らかだ。
赤頂点を $s$ に近い順に $0,1,2, \cdots ,|A|-1$ 、青頂点を同様に $0,1,2, \cdots ,|B|-1$ とラベル付けし、 $(x,y)$ をラベルで表したものを $(u,v)$ とする。
$[1]$ を辺についてラベルで表すと、
- 赤頂点 $a$ と青頂点 $b$ を結ぶ辺があるならば、 $(u \leq a$ かつ $v \leq b)$ または $(a \leq u$ かつ $b \leq v)$ を満たす。
となる。これを $a$ についてまとめると、 $\text{minV}[a],\text{maxV}[a]$ $(0 \leq a \leq |A|-1)$ の値を適切に定めることで
- $0\leq a\leq |A|-1$ について、 $(u \leq a$ ならば $v \leq \text{maxV}[a])$ かつ $(a \leq u$ ならば $\text{minV}[a] \leq v)$ を満たす。
と表せる。 $\text{maxV}[a]$ を $a$ の小さい側に伝播、 $\text{minV}[a]$ を $a$ の大きい側に伝播すると、
- $\text{minV}[u] \leq v \leq \text{maxV}[u]$
と簡単に求められるようになる。数え上げも各 $u$ に対して $\max\{0,\text{maxV}[u]-\text{minV}[u]+1\}$ として求められる。(証明終)
あとがき・宣伝
一発芸の割には難しいはずです。しかし行間これだけ詰めたら読めるだろ！
block-cut tree の verify におすすめのジャッジです。なお、この verify 問題にある私の解説は証明が不十分です。2021年11月4日現在、 Library Checker には block-cut tree の verify 用問題はありません。
(2022/08/31更新) Library Checker に block-cut tree 相当の問題が生えました。やったね
