ABC204 C – Tour

はじめに

競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC204 C – Tourを解きました。

難易度は茶色。

考察

幅優先探索で全通り試すと、計算量はO(N^2)になる（たぶん？）

制約は N < 2000 なので十分間に合いそう。

コード

from collections import deque
INF = pow(10, 18) + 7
NULL = -1

N, M = map(int,input().split())
R = [[] for i in range(N+1)]
ans = 0

for i in range(M):
    a, b = map(int,input().split())
    R[a].append(b)

def bfs(s):
    global ans
    que = deque([])
    dist = [NULL]*(N+1)
    dist[s] = 0
    ans += 1
    que.append(s)

    while que:
        pos = que.popleft()
        for v in R[pos]:
            if dist[v] != NULL:
                continue
            dist[v] = dist[pos] + 1
            ans += 1
            que.append(v)
    return dist

for i in range(1, N+1):
    bfs(i)

print(ans)

まとめ

幅優先探索のべた張りで一瞬で解けました。

これで茶Diffの上の方なので、グラフの勉強は大切ですね。。