Dynamic connectivity contest: GraphAero

問題ページ

とりあえず LC 木で解けるので解きました。ただこの方法だと D 問題が解けない。

問題概要

N 頂点 M 辺の無向グラフが与えられる。辺(u,v) を追加するというクエリが K 個与えられるので順次処理せよ。各クエリを処理した後、グラフ中にある橋の数を出力せよ。

• 1≦N,M,K≦10⁵

解法

• 辺追加時にサイクルが生じない場合、その辺は橋である
• 辺追加時にサイクルが生じる場合、そのサイクル内の辺は橋ではない

ということを考える。これを高速に処理するには辺更新に対応した link-cut tree を用いれば良い。

辺更新は u→v という辺を張らずに、u→e→v のように間に辺のノードを挟んでおけば簡単。

GraphAero

D はもう少し考える。