ABC225 B Dif:62 『AtCoder ABC201~225 ARC119~128 灰・茶・緑問題 超詳細解説』サンプル

この記事は 『AtCoder ABC201~225 ARC119~128 灰・茶・緑問題 超詳細解説』 のサンプルです。

【その他のサンプル】
ABC201 A：https://qiita.com/sano192/items/3258c39988187759f756
ABC213 C：https://qiita.com/sano192/items/9cd14b2cefd8bafa5615
ABC221 D：https://qiita.com/sano192/items/8679200f0f89e636b354
ARC122 B：https://qiita.com/sano192/items/1f314701f2d5b18c8816

「ものすごく丁寧でわかりやすいABC解説」シリーズをベースに【キーワード】【どう考える？】【別解】を追加し、【解説】と【実装のコツ】を分けることでよりわかりやすく、具体例や図もより豊富に全ての問題の解説を書き直しました！
さらにQiitaでは公開していないARC119~128の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！

値段：300円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

【キーワード】
なし

【どう考える？】
問題文を読むだけでは「スター」というのがどういうものか分かりづらい。入力例を紙に書いてみて、どのような条件なのか確認しよう。
紙に書いてみると各頂点に対してつながっている辺の本数で「スター」かどうか判定できることがわかる。(N-1)本の辺がつながっている頂点があるかないかで場合分けを行えば良い。

【解説】
まず「スター」であるというのはどういう状態か、入力例1を紙に書いて確認しよう。

「入力例1」
N：5
a1 b1：1 4
a2 b2：2 4
a3 b3：3 4
a4 b4：4 5

これは「スター」である。確かに頂点④から他の全ての頂点へ辺がつながっている。

各頂点に対し、出ている辺の本数を確認し
・(N-1)本の辺が出ている頂点がある→「Yes」を出力
・上記以外→「No」を出力
とすればよい。

【実装のコツ】
＜途中終了＞
(N-1)本の辺が出ている頂点が一つでもあれば「Yes」を出力して終了する。

途中終了する場合は
exit()
と書く。

【提出】

提出　

# 入力の受け取り
N=int(input())

# 辺の本数を数える
count=[0]*(N+1)

# (N-1)回
for i in range(N-1):
    # 入力の受け取り
    a,b=map(int, input().split())
    # a,bから出ている辺の数を数える
    count[a]+=1
    count[b]+=1

# i=1~N
for i in range(1,N+1):
    # 頂点iから出ている辺が(N-1)本なら
    if count[i]==N-1:
        # 「Yes」を出力
        print("Yes")
        # プログラムの終了
        exit()

# 「No」を出力
print("No")