[伯俊-2644]カウント

6121 ワード
BFS/DFS テキストリンク

質問する


リンク

コード#コード#

from collections import deque
n = int(input())
a, b = map(int, input().split())

m = int(input())

fam = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m) :
    x, y = map(int, input().split())
    fam[x].append(y)
    fam[y].append(x)
    
queue = deque()
queue.append(a)
while queue : 
    q = queue.popleft()
    for f in fam[q] :
        if visited[f] == 0 :
            queue.append(f)
            visited[f] = visited[q] + 1
            if f == b :
                break

if visited[b] == 0 :
    print(-1)
else :
    print(visited[b])

に答える


幅優先探索(BFS)で問題を解く.
  • インチを計算する必要がある2人のうち、1つの番号をキューに入れます.
  • whileドア内から一番前の番号が飛び出します.このときwhileはQが許しを請うまで
  • は、この番号に関連付けられた番号のうち、アクセスしたことのないすべての番号をキューに入れる.このとき,接続されたアクセス番号はその番号のアクセス値+1となる.
    3-1. このとき、もう一つの寸法を計算する必要がある番号であれば、繰り返し文を停止します.
    3-2. あるいは2番に戻ります.
  • この番号のアクセス番号が0より大きいと出力を示し、0は親戚関係が全くないことを示すため、−1を出力する.
    • 19.3 Function template specialization
    バインドとは?( Feat . this )