ユニークビジョンプログラミングコンテスト2023 新春 C問題解説(Pythonコード例付)

はじめに　

　本記事はPythonでAtcoderにチャレンジしているけど、Pythonはコード例がないため解説がわかりにくい！と感じている方を対象としています。
　私自身大してレートも高くないので、不備等あるかもしれませんがご了承くださいm(_ _)m
　質問や指摘などもコメント等に書いてくださったら対応していきたいと考えていますのでどしどしコメントしてください。(内容がわかりにくいぞ！みたいな文句でもオールオッケーです笑)

ユニークビジョンプログラミングコンテスト2023 新春 C問題

　問題のURLはこちらです。ユニークビジョンプログラミングコンテスト2023 新春 C問題

使う手法

　UnionFind木を使います。　
　正直自分もあまり理解できていませんが、UnionFind木はデータ構造の一つで、データのグループ管理を楽にしてくれるものらしいです。　
　実装例はこちらにありますので、参考にしてみてください。(というか、自分はUnionFindを使いたい時こちらのサイトの実装例を丸コピして使わせてもらっています笑)

考え方　

　公式解説と同じことをやっていきます。　
　パスグラフの条件は　
　・グラフの数が一つであること
　・次数(各頂点から伸びる辺の数)が1つないし2つであり、次数が1の頂点を二つ持つ　
　の2つが、パスグラフの条件となっています。　
　従って、まずはグラフの数がひとつかどうかをUnionFindを用いて調べて、グラフの数が1つであるなら各頂点の次数を調べていくことで、パスグラフか否かを判定していきます。

実装例　

from collections import defaultdict
#UnionFindクラスの構築(添付したURL先のコード丸コピ) 
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
 
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
 
  def size(self, x):
    return -self.parents[self.find(x)]
 
  def same(self, x, y):
    return self.find(x) == self.find(y)
 
  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]
 
  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
 
  def group_count(self):
    return len(self.roots())
 
  def all_group_members(self):
    group_members = defaultdict(list)
    for member in range(self.n):
      group_members[self.find(member)].append(member)
    return group_members
 
  def __str__(self):
    return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())
 
#標準入力
n,m = map(int,input().split())

#ufの構築
uf = UnionFind(n)
#辺同士の繋がりを管理する辞書「dic」を作成 
dic = dict()
#dicは各頂点をキーとし、辺で結ばれた頂点をリストで管理。　
#初期状態としてからのリストを配置
for i in range(n):
  dic[i+1] = list()
#各辺の入力を受け取る 
for i in range(m):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)
  dic[a].append(b)
  dic[b].append(a)
"""
次数が1の頂点をカウントする値「count_1」と、
次数が2の頂点をカウントする値「count_2」と、　
判定のフラグである「booler」を作成。
"""
count_1 = 0
count_2 = 0
booler = True

#グラフの数がひとつか否かをを判定
if uf.group_count() == 1 :
  #ひとつであるなら、各頂点の次数を調べて行く
  #次数が3以上の頂点がある場合、問答無用でパスグラフでないので弾く
　#次数が1ならcount_1を、2ならcount_2の値を増やしていく
  for i in range(n):
    l = dic[i+1]
    if len(l) == 1 :
      count_1 += 1
    elif len(l) == 2 :
      count_2 += 1
    else :
      booler = False
      break     
else :
  booler = False

#次数を調べ終わり、パスグラフの条件を満たすかどうか判定
if (count_1 != 2) or (count_1+count_2 != n):
  booler = False
  
if booler :
  print("Yes")
else:
  print("No")

感想

　自分は今回、深さ優先探索を使って解こうとしていましたが、再帰関数の実装がうまくいかずに今問題を解くことができませんでした。　
　UnionFindを使うことも一瞬頭によぎりましたが、UnionFind自体をグルーピングで使えるものとしか思っておらず、解説されていた解法に辿り着けませんでした。　
　調子に乗って年末辺りから解説記事なんて書き始めましたが、実装力、発想力、知識全てにおいて実力不足を実感した問題でした。　
　悔しくてたまらないので今日のARCは頑張りたいと思います。