【AtCoder】ABC334 G - Christmas Color Grid 2

問題のリンク

解法1（LowLink）

LowLinkのアルゴリズムをベースに少し改良を行い実装する。

ところで、LowLinkを改良するアルゴリズムを考えるときには、（実際にはまとめて行っているが）まずDFS Treeをとり、そのDFS Tree上にある辺かそうでない辺（後退辺）であるかで処理を場合明けしてもう一度DFSを行っているとイメージするとわかりやすいと感じた。（DFS Treeを強く意識するのが良い。） また、ordとlowはdp[i]を後退辺をi回通ったものしてそれぞれdp[0]とdp[1]という考え方をすると良いかもしれない。

#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "graph/low_link.hpp"
#include "math/static_modint.hpp"
using mint = mint998;
using namespace std;

int main() {
    INT(H, W);
    auto [G, id, loc] = read_grid(H, W);
    int N = LEN(G);
    LowLink lnk(G);
    mint ans = 0;
    REP(i, N) ans += lnk.count_components() - 1 + lnk.count_components_remove(i);
    ans /= N;
    print(ans);
    return 0;
}

解法2（分割統治法）

Undo可能UnionFindを使うらしい。（時間のあるときに書く）

感想

LowLinkが橋・関節点列挙のアルゴリズムというのは知っていたが、使い道をよく知らなかったので勉強になった。 今回の場合は無向グラフにおいて頂点を1つ削除したときの連結成分数の変化を前計算 クエリ で行っていると言える。