blog.bouzuya.net

2023-01-02 ABC266 の F と ABC154 の A, B, C, D を解いた

ABC266 : AtCoder Beginner Contest 266 の F を解いた。

  • F - Well-defined Path Queries on a Namori https://atcoder.jp/contests/abc266/tasks/abc266_f
    • 提出: https://atcoder.jp/contests/abc266/submissions/37675514
    • 解説 AC
    • N 頂点 N 辺の連結な単純無向グラフは、木に 1 つ辺を足したもの (なもりグラフ)
    • 閉路が 1 個あり、その中の頂点から「足」 (木) が生えている構造
    • ひとつの「足」の中の頂点 2 つならパスは 1 つ (Yes) 、そうでなければ閉路を通るので複数 (No) になる
    • 辺の数 (次数) が 1 個の頂点から辺をたどって、たどった辺は削除し、辺を削除した頂点の辺の数が 1 個になれば……と続ける
    • たどりながら Union-Find (Dsu) で連結して同じグループにしていく (「足」でまとめる)
    • 各クエリに対して Union-Find で同じグループかを判定する

ABC154 : AtCoder Beginner Contest 154 の A, B, C, D を解いた。


今日のコミット。