競プロ典型 90 問：078 - Easy Graph Problem（★2）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/11/01
• 結果：解けた
• 時間：10分

考えたこと

• グラフをマトリックスで持つと、1頂点について確認するのにグラフをナメないと行けないのでTLEするのかなと思った。
• グラフを集合もってもナメないとダメなので、優先度付きキューで持てばlogで抑えられそうかなと思った。
• そんなことを考えていたけど、翌々考えたらノード番号より小さい方だけをカウントすれば良いだけと気がついた。
• カウントしてみて、1の数をカウントすればOK。
  • pythonのfilter関数を使って見たけど、count関数のほうがシンプルだった

公式解説

https://twitter.com/e869120/status/1409644684561944579

解説を読んだふりかえり

• ★2ということもあって、グラフの基本を知ろうというのがテーマだったらしい。
• この問題については隣接グラフはMLEで、隣接リスト形式を使おうというのがテーマだったらしい。作成者の意図に反した解法になっているのかも。

ソース

N,M = [int(x) for x in input().split()]

# Cは自分自身より頂点番号が小さいものの数
C = [0] * (N+1)
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    # aを小さい方とする
    a,b = min(a,b), max(a,b)
    # b(大きい方)
    C[b] += 1

# 1の数を数える
print(C.count(1))