【競プロ典型90問】「078 - Easy Graph Problem(★2) 」解法
Free-PhotosによるPixabayからの画像

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。

問題

078 - Easy Graph Problem(★2)

ポイント

はじめに各頂点の隣接頂点のグラフを作成し、その後条件に当てはまる頂点を探索していきます。

コード

def main():
    import sys
    sys.setrecursionlimit(10 ** 9)
    input = sys.stdin.readline

    N, M = map(int, input().split(" "))
    graph = [[] for _ in range(N + 1)]

    # 各頂点の隣接頂点のグラフ作成
    for _ in range(M):
        a, b = map(int, input().split(" "))
        graph[a].append(b)
        graph[b].append(a)

    # 条件に当てはまる頂点の探索
    ans = 0
    for i in range(1, N + 1):  # 頂点は1スタート
        if len(graph[i]) == 1:  # 隣接頂点が1つだけならばそれが自分自身より小さいかを検証
            if graph[i][0] < i:
                ans += 1
        else:
            graph[i].sort()
            if graph[i][0] < i and graph[i][1] > i:  # 1番目が自分より小さく2番目が自分より大きいか検証
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

おすすめの記事