Solve ABC168D in Python

Introduction

I couldn't solve it at ABC yesterday, and I was frustrated and couldn't sleep at night, so I'll review it.

** Thoughts ** Due to restrictions, the graphs given are concatenated because it is possible to move between rooms using multiple roads. If it is a connected graph, it will always be like construction. If you submit it with print ('No'), it will be 0AC. The solution is to search for the signpost from 1 to the same depth, and when you reach a room deeper than you, place the signpost to your room. This is easy to implement in BFS.

ver is a list of rooms that can be reached from ver [i] in one go

from collections import deque
n, m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

q = deque([])
path = [-1] * n
ver = [[] for _ in range(n)]
for i in range(m):
    ab[i].sort()
    if ab[i][0] == 1:
        q.append([ab[i][0]-1,ab[i][1]-1])
        #path[ab[i][1]-1] = 1
    ver[ab[i][0]-1].append(ab[i][1]-1)
    ver[ab[i][1]-1].append(ab[i][0]-1)

def bfs(q, visited_list):
    while len(q) > 0:
        now = q.popleft()
        go = now[1]
        if visited_list[go] == -1:
            visited_list[go] = now[0]+1
            for i in range(len(ver[go])):
                q.append([go,ver[go][i]])
    return visited_list
ans = bfs(q,path)
print('Yes')
for i in range(1,n):
    print(ans[i])

Computational complexity is $ O (N + M) $

Summary

It was a very basic problem. Yesterday, I felt like I was spinning, so I will do my best to complete one at the next AGC. see you.

Digression

Graph problems are easy to think of using this.