トップ > AtCoder > ABC226E - Just one

ABC226E - Just one

AtCoder AtCoder-Beginner Contest グラフ UnionFind Python

考え方

連結成分ごとの答えをかけ合わせれば良い．

「どの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在する」とき，頂点と辺は1セットと考えることができ

  • (頂点数) = (辺数)
という条件を満たす．また，「(頂点数) = (辺数)」であるとき 「ループが唯一つ存在する」．


逆に，「(頂点数) = (辺数)」であれば「どの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在する」．具体的には，

  • ループの外の辺は，ループに向かうように向きづけし，
  • ループの向きは，2通りのうち片方を選べばよい

以上より，各連結成分の向きの付け方は，ループの向きだけとなる．


まとめると，各連結成分の向き付けの方法を

  1. 「(頂点数) = (辺数)」なら向き付けの方法は2通り
  2. 「(頂点数) ≠ (辺数)」なら向き付けの方法は0通り
として，すべての連結成分の結果をかけ合わせれば良い．


回答例

import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
mod = 998244353

p = [-1] * (N + 1)
def root(x):
  if p[x] < 0:
    return x
  p[x] = root(p[x])
  return p[x]
 
def unite(x, y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  p[x] += p[y]
  p[y] = x

def size(x):
  x = root(x)
  return -p[x]
  
edge = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  if root(u) != root(v):
    edge[root(u)] += edge[root(v)] + 1
  else:
    edge[root(u)] += 1
  unite(u, v)
  
  
ans = 1
for v in range(1, N + 1):
  if v != root(v):
    continue
  if size(v) == edge[v]:
    ans *= 2
    ans %= mod
  else:
    ans = 0
  
print(ans)

ここでは，edgeで各連結成分の辺の数を，edge[根]で管理した．


他の計算方法として，次の回答では，

  • 各頂点から出ている辺の本数degreeを計算し，
  • 全部計算が終わったところで，連結成分に属する頂点から出ている辺の本数の合計値degree_cnt[根]を計算し，
  • 連結成分の辺の数をdegree_cnt[根] // 2で求める，
としている．
【競プロ実況】ABC226 E問題【かつっぱ】 - YouTube (Submission #27093388 - AtCoder Beginner Contest 226)

参考