このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
ポイント
はじめに各頂点の隣接頂点のグラフを作成し、その後条件に当てはまる頂点を探索していきます。
コード
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()
