DFS木・lowlink

参考資料

橋と関節点, lowlink - Lilliput Steps
二重辺連結成分分解(Two-Edge-Connected-Components) | Luzhiled’s memo
競技プログラミングにおける無向グラフに関する（橋、関節点、サイクル基底、lowlink）問題まとめ - はまやんはまやんはまやん

DFS木

$n$ 頂点 $m$ 辺の無向グラフ $G(V,E)$
DFS木: 頂点 $v \in V$ を始点として，各頂点に高々1度しか訪れないようにDFSを行う．使用した辺からなる木をDFS木と呼ぶ．この木は根を $v$ とする根付き木である．
後退辺: DFS木で使わなかった辺のうち，葉から根の方向の辺

有向グラフでDFS木を考えると前進辺とか横断辺とかもあったりする．
前進辺: DFS木で使わなかった辺のうち，根から葉の方向の辺
横断辺: DFS木で使わなかった辺のうち，深さが同じ頂点間の辺

無向グラフのDFS木には前進辺，横断辺が存在しないなど扱いやすい．グラフの構築とかでDFS木を使うと嬉しいことがある．
ToDo: 全域木とサイクル基底の関連性

WUPC2019 C - Permutation City

DFS木で最短距離が1 or 2になるような順列を作成する．このとき，後退辺を使用して最短距離が0や2以上になることはない．したがって，DFS木の辺のみを考えたとしても，条件を満たすような順列は作成できる．
DFS木の葉の方から順番に $p_i$ を決めていくことでこの順列は求まる．

提出

Codeforces Round #434 Div.1 D. Wizard's Tour

概要
$n$ 頂点 $m$ 辺の無向グラフが与えられる．辺が被らないように経路 $x \to y \to z$ を取るとき，経路の個数を最大化しろ．

DFS木でボトムアップで決めていく． $v$ から伸びる辺のうち，

後退辺
親との辺 $(v,p)$
$c$ ですでに親との辺を使っていない子へ伸びる辺 $(v,c)$

が使用できる辺である．偶数本であればそれらを全て組み合わせる．奇数本であれば $(v,p)$ 以外の辺を全て組み合わせる．このように決めると $\lfloor M/2 \rfloor$ 個の経路を取ることができ，最適である．

提出

長さが0のサイクルが存在するか⇔dist[to]が一意に定まる．
書き換える対象にする辺(u,v)を消して，dist[to]を求める．dist[to]が一意に定まればよい．書き換える辺に関わらないサイクルの長さが0であることが，これで判定できる．
ただし，全ての辺に対してDFSを行うと $O(M^2)$ でTLEしてしまう．頂点 $v$ に入る辺を消した場合，どの辺であってもdistは全て一致するため，複数回DFSを行う必要がない．
DFSを行ったあと dist[u]+(u→vの重み) = 0 でないような辺が存在した場合，書き換えなければならない．このような辺が高々1つなら，条件が達成できる．よって，各頂点に入る辺を消してDFSを行い，この条件を達成できる頂点が存在すれば"Yes"を出力する．

提出

公式解説のDFS木を使う解法
辺 $(u,v,d)$ が存在したとき逆辺 $(v,u,-d)$ を追加しても答えは変化しない．逆辺を追加して無向グラフのように扱う．
DFS木で頂点 $v$ までの距離を $h_v$ とする．このとき「辺 $(u,v,d)$ が存在するとき $d=h_v-h_u \iff$ 問題の条件を満たす」である．辺を取り除いてDFS木をつくって確かめるとすれば，上の解法と同様に $O(M^2)$ となる．
長さが0でないサイクルを見つけられれば，取り除く辺の候補を $O(N)$ 個に限定でき， $O(NM)$ でできる．後退辺 $(u,v)$ で条件を満たさなかった場合，DFS木上の $v$ から $u$ へのパスと $(u,v)$ からなるサイクルがこの候補となる．

Codeforces Round #453 Div1 D - Weighting a Tree

概要
$n$ 頂点 $m$ 辺のグラフが与えられる．辺の重みを設定し，頂点の重みと隣接する辺の重みの和が一致するようにできるか？
$n.m \leq 10^5$

DFS木の後退辺の重みを0，DFS木の辺の重みを非負としたときに達成可能か考える．

葉に隣接する辺については一意に決定できる．葉の方からボトムアップで参照していくことで，根以外の頂点について値を一致させられるような辺の重みの決め方が存在する．この時点で根の値も一致するのであればこれを出力する．

根の値が一致していなければ，後退辺を用いて根の値を調整する．DFS木のパス $u \to v$ と後退辺 $v \to u$ からなる閉路を考える．以下のように辺の重みを変化させると，根以外の値を変化させずにrootの値を変化させることができる．

f:id:ferin_tech:20191121224758j:plain

この閉路が偶数長
閉路に属する頂点の値を変更させずに，他の頂点の値を変更させることはできない．
この閉路が奇数長
- root と $u$ の距離が偶数
  後退辺の重みを $a$ にすると，rootの値が $+2a$ される
- root と $u$ の距離が奇数
  後退辺の重みを $a$ にすると，rootの値が $-2a$ される

提出

lowlink

$\text{ord}_v$ を頂点 $v$ を訪れるタイミングとする．後退辺を高々1度だけ用いて到達できる頂点の $\text{ord}$ の値の最小値をlowlinkと呼ぶ．各頂点 $v$ についてこの値は $\text{low}_v$ で表す．

lowlinkはdfsを行えば求められる．

vector<ll> g[N];  
bool visit[N];  
ll ord[N], low[N];  
void dfs(ll v, ll p, ll &k) {  
    visit[v] = true;  
    ord[v] = k++;  
    low[v] = ord[v];  
    for(auto to: g[v]) {  
        if(!visit[to]) {  
            dfs(to, v, k);  
            // 子まで進み，その子から後退辺を使うことで low[to] を達成できる  
            chmin(low[v], low[to]);  
        }   
        // 後退辺を使う場合は ord[to] を達成できる  
        chmin(low[v], ord[to]);  
    }  
}

橋・二重辺連結成分

DFS木の辺 $(u,v)$ が橋 $\iff \text{ord}_u \lt \text{low}_v$
DFS木の辺 $(u,v)$ の両端が同じ二重辺連結成分 $\iff \text{ord}_u \geq \text{low}_v$
を用いて橋の検出や二重辺連結成分分解を行える

実装

ARC039 D - 旅行会社高橋君

二重辺連結成分分解したあとの木で $a \to c$ の途中に $b$ が存在するか？を判定できればよい．これは $\text{dist}(a,b)+\text{dist}(b,c) = \text{dist}(a,c)$ で判定できる．木の2点間の距離はLCAを用いることで高速に求められるので解けた．

提出

ICPC 2019 Asia Yokohama Regional I One-Way Conveyors

問題の解説自体は ICPC 2019 Asia Yokohama Regional I One-Way Conveyors - ferinの競プロ帳に書きました．

二重辺連結成分内の任意の頂点対を行き来できるように辺の向きを定めるパートがある．DFS木に含まれる辺は根から子の方向，後退辺は子から根の方向に向きを定める．二重辺連結成分には橋が存在しないことから，後退辺がDFS木の各辺と最低1回は交差するため，各頂点が行き来可能であることが言える．

145行目～159行目が該当の処理
提出

関節点・二重連結成分

関節点
* DFS木の根
頂点の次数が2以上なら関節点
* 根以外
$u$ が関節点 $\iff \text{ord}_u \leq \text{low}_v$ が成り立つ頂点 $u$ の子 $v$ が存在

実装

二重連結成分
辺集合が素な辺集合の和になるように関節点で分割する．辺集合と関節点を頂点にして，関節点と辺集合が隣接しているなら辺で結ぶとすると木(Block-Cut Tree)が得られる．
https://en.wikipedia.org/wiki/Biconnected_component