[python]白準/白銀/1325:高効率ハッカー

14583 ワード
コーディングテスト テキストリンク
質問リンク:https://www.acmicpc.net/problem/1325
これはBFSの問題です.これはBFS実行プロセスを見直すことができる問題のようである.この問題では,図には周期があり,方向図がある.当初,BFSキューにノード番号とnumを挿入し,次のノードをブラウズするたびにnumが増加することを実現し,反例を生じた.
Qを探索する過程で,Qに変数を加えて操作するか,グローバル変数として操作するかを把握する必要があると思う.

ふごうコード

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[B].append(A)

howManyHack = [0] * (N+1)

for i in range(1, N+1):
    visit = [False] * (N + 1)
    howMany = 1
    # BFS
    q = deque()
    q.append((i, 1))
    visit[i] = True
    while q:
        now, num = q.popleft()
        for x in graph[now]:
            if not visit[x]:
                q.append((x, num+1))
                howMany = max(howMany, num+1)
                visit[x] = True
    howManyHack[i] = howMany

print(howManyHack)
answer = ""
for i in range(1, N+1):
    if howManyHack[i] == max(howManyHack):
        answer += str(i)+" "

print(answer[:-1])

反例



1ノードもhowManyHack値が2、2ノードもhowManyHack値が2のため、エラー処理されます.

正解Pythonコード

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[B].append(A)

howManyHack = [0] * (N+1)

for i in range(1, N+1):
    visit = [False] * (N + 1)
    howMany = 1
    # BFS
    q = deque()
    q.append(i)
    visit[i] = True
    while q:
        now = q.popleft()
        for x in graph[now]:
            if not visit[x]:
                q.append(x)
                howMany += 1
                visit[x] = True
    howManyHack[i] = howMany

#print(howManyHack)
answer = ""
for i in range(1, N+1):
    if howManyHack[i] == max(howManyHack):
        answer += str(i)+" "

print(answer[:-1])
Array method
01-Bootstrapベース