There is a cave somewhere. The cave has N rooms and M passages, with rooms numbered 1 to N and passages numbered 1 to M. Passage i connects room Ai and room Bi in both directions. You can walk back and forth between the two rooms through several aisles. Room 1 is a special room with a cave entrance. The inside of the cave is dim, so I decided to set up one guide in each room except room 1. The trail for each room should point to one of the rooms that is directly connected to that room by a passageway. Since the inside of the cave is dangerous, the goal is to meet the following conditions for all rooms except Room 1. If you start from that room and repeat "look at the road sign in the room you are in and move to the room it points to", Get to Room 1 with the least number of moves. Determine if there is an arrangement of trails that can achieve your goal, and if so, output one such arrangement.
from collections import deque
mi = lambda:list(map(int,input().split()))
mix = lambda x:list(mi() for _ in range(x))
##########
def main(n,m,l):
#Creating a graph
g = creategraph(n,l)
#NG if there is a separate room
for i in range(1,len(g)):
if len(g[i]) == 0:
print("No")
return
#Create a signpost with BFS
navi = bfs(n,g)
#NG if the signpost of the room except room 1 is not updated
if min(navi[2:]) == 0:
print("No")
else:
print("Yes")
for i in navi[2:]:
print(i)
#BFS breadth-first search
def bfs(n,g):
navi = [0]*(n+1)
navi[1] = -1
q = deque()
q.append(1)
while len(q) > 0:
#Take your current location from the queue
cp = q.popleft()
#Get a list of adjacent points at your current location
np = g[cp]
#If the adjacent point has not been searched, queue it + update the signpost
for i in np:
if navi[i] == 0:
navi[i] = cp
q.append(i)
return navi
#Generate a list that holds the adjacencies of each Node
def creategraph(n,l):
g = {i:[] for i in range(n+1)}
for a,b in l:
g[a].append(b)
g[b].append(a)
return g
def resolve():
n,m = mi()
l = mix(m)
main(n,m,l)
if __name__ == "__main__":
resolve()
Recommended Posts