Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 226 E 問題 Just one

AtCoder ABC ABC226 E問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点, $M$ 辺の単純無向グラフ $G$ が与えられる. $G$ の全ての辺の向き付けのうち, 全ての頂点の出次数が1になるような向き付けは何通りか?

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
グラフは単純

解法

まず, $G$ のある連結成分における向き付けは他の連結成分の向き付けに影響を与えず, 独立に考えることができる. よって, 各連結成分についての議論を行い, 最後に全ての連結成分における答えの総積を求めることになる.

$G$ は連結であるとする. まず, 辺に向き付けると, そのグラフの出次数の総和が1だけ増える. このことから, 条件を満たすような向き付けが存在するならば, $N=M$ となる. このことから, $N \neq M$ ならば, 答えは $0$ になる.

$N=M$ とする. このとき, $N$ 頂点, $N$ 辺の連結グラフになるので, 以下の事がわかる.

$G-e$ が木になるような辺 $e$ が存在する.

また, 木に関して, 以下のことがわかる (実は同値)

$T=(V,E)$ が木であるとき, $u,v \in V$ で, $uv \in E$ ならば, $T+e$ はちょうど1つのサイクルをもち, そのサイクルは辺 $uv$ を含む.

ここで, 辺 $e$ を, $G-e$ が連結になるような辺とする. このとき, $e$ に向き付けると, 以下のような理由により, 必ず条件を満たすような向き付けが唯一存在する.

$G$ にある唯一のサイクルを $C$ とする. $C$ の向き付けは $e$ の向き付けから, 自然に定まる.
$G-C$ の辺は, $C$ に向かう向きでないといけない. 厳密には, $C$ 上の頂点 $w$ を適当にとり, 葉 $v$ に対して, ( $C$ 上での向きを保って) $vw$ -Path による向きづけになる.

$e$ の向き付けは2通りであるので, $N=M$ のときは2通りである.

以上から, 連結成分での議論を終えたので, 求めるべきと答えは, $G$ の連結成分の個数を $K$ , 各連結成分 $B$ における頂点, 辺の数を $N(B), M(B)$ としたとき.

全ての連結成分 $B$ で, $N(B)=M(B)$ ならば, $2^K$ 通り.
$N(B) \neq M(B)$ となる連結成分 $B$ が存在すれば, $0$ 通り.

計算量は各連結成分の頂点数と辺の数をBFSやDFS, または Union-Find を用いて記録することにより, それぞれ $O(N+M), O( (N+M) \alpha(N) )$ で求めることができる.