2022-02-21 ABC239 F - Construct Highway を解いた
デンソークリエイトプログラミングコンテスト2022 ( ABC239 : AtCoder Beginner Contest 239 ) F - Construct Highway を解いた。
問題: https://atcoder.jp/contests/abc239/tasks/abc239_f
本番では解けなかった。 N 頂点 N - 1 辺で連結なので木になることは分かった。入次数・出次数の和は 2 * (N - 1) なのも分かる。 D_i の和が 2 * (N - 1) でない場合は NG 。 DSU (Union-Find) を使って連結成分を調べた。既存の辺が連結済みの頂点を再度追加している場合は NG 。あとは非連結の頂点を結ぶ辺を追加していくだけだったのだけどうまく実装できなかった。
解説: https://atcoder.jp/contests/abc239/editorial/3388
解説によると連結成分ごとに次数の残っている頂点をまとめておき、 1 ものと 2 以上のものを連結し、最後に何も残らないか次数 1 のものが 2 つだけ残っていると良いらしい。解説を読んでからもなかなかうまく実装できなかった。難しい……。
提出: https://atcoder.jp/contests/abc239/submissions/29557047
今日のコミット。