[Python] BFS (breadth-first search) ABC168D

ABC168D

Note that since it is a connected graph, the minimum is guaranteed by the principle of BFS.

reference BFS (Breadth-first Search) Super Introduction! ~ Use the queue vividly ~

Sample code


from collections import deque

#Number of vertices and sides
N, M = map(int, input().split())
#Edge
AB = [map(int, input().split()) for _ in range(M)]

#Adjacency list settings for undirected graphs
link = [[] for _ in range(N + 1)]
for a, b in AB:
  link[a].append(b)
  link[b].append(a)
    
#BFS data frame
dist = [-1] * (N + 1)  #No sign set
que = deque([1])       #Visit queue starting from vertex 1

#BFS start(Search until the queue is empty)
while que:
    v = que.popleft() #First vertex from queue(Current location)v get
    
    for i in link[v]:
      #Set a sign to the current location at the unset vertex i and add it to the visit queue
      if dist[i] == -1:
        dist[i] = v
        que.append(i)

#Result output (signboard installed at each vertex)
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))

Recommended Posts

[Python] BFS (breadth-first search) ABC168D
[Python] BFS (breadth-first search) ABC007C
Algorithm in Python (breadth-first search, bfs)
Python Exercise 1-Breadth-first search
[Python] Binary search ABC155D
Breadth-first search / bidirectional search (Python version)
[Python] DFS (Depth-first Search) ABC157D
[Python] Depth-first search and breadth-first search
[Python] ABC175D
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Breadth-first search (BPF) Maybe understood (python)
[Python] 01-BFS ARC005C
[Python] DP ABC184D
[Python] UnionFind ABC177D
Solve ABC168D in Python
Sequential search with Python
Solve ABC167-D in Python
[Python] Interval scheduling ABC103D
[Python] Search (itertools) ABC167C
[Python] Cumulative sum ABC186D
Binary search in Python
[Python] Search (NumPy) ABC165C
Binary search (python2.7) memo
Solve ABC159-D in Python
python bit full search
Linear search in Python
Binary search with python
Binary search with Python3
Search Twitter using Python
[Python] Dynamic programming ABC015D
Binary search in Python (binary search)
[Python] Cumulative sum ABC179D
I implemented breadth-first search in python (queue, drawing self-made)
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Search for strings in Python
Search algorithm using word2vec [python]
Homebrew Python --Youtube Search Program
[Python] DFS (Depth-first Search) ATC001A
ABC161D Lunlun Number with python3
Binary search in Python / C ++
Algorithm in Python (binary search)
Full bit search with Python
Find the diameter of the graph by breadth-first search (Python memory)
Search engine work with python
Search twitter tweets with python
Streamline web search with python
Write a binary search in Python
[Python] How to derive nCk (ABC156-D)
Learn search with Python # 2bit search, permutation search
Algorithm in Python (depth-first search, dfs)
Master linear search! ~ Python implementation version ~
Write a depth-first search in Python
(Python) ABC162-D Consideration log and solution
Reproduce One-Touch Search on Python 3.7.3. (Windows 10)
Depth-first search using stack in Python
Python 2-minute search and its derivation
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search