アルゴリズム実技検定(PAST) 第11回 G問題 Python解答例(木の判定)

Supershipの名畑です。
今年も残り3日半ですね。

アルゴリズム実技検定(PAST)の過去問シリーズです。第11回G問題の私の解答例(Python3)を公開します。

「そもそもアルゴリズム実技検定ってなんですか？」という方はこちらの記事を合わせてご覧いただけますと幸いです。

第11回 G問題 木の判定

問題

G - 木の判定

言語

• Python (3.8.2)

解答例

グラフにおける木の条件を

• すべての頂点が連結している
• 閉路を持たない

とすると辺数がN-1であることが問題で保証されているため、前者が満たされれば後者も満たされる。

N = int(input())

# 各頂点が他の頂点と連結されているかどうかを格納
tree = [False] * (N + 1)

for i in range(N - 1):
    a, b = map(int, input().split())

    # aとbを連結済みとする
    tree[a] = True
    tree[b] = True

tree[0] = True  # 頂点0は存在しないためTrueにしておく
for val in tree:
    if not val:
        print("No")
        exit()
print("Yes")

宣伝

SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。

Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。

是非ともよろしくお願いいたします。