[Python] [BFS] At Coder Beginner Contest 168-D [.. Double Dots]

Problem statement (.. Double Dots)

ABC168-D Double Dots

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.

answer

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

[Python] [BFS] At Coder Beginner Contest 168-D [.. Double Dots]
[At Coder] Beginner Contest 175 ABCD python Solution introduction
AtCoder Beginner Contest: D Question Answers Python
[Python] Competitive template [At Coder]
Atcoder Beginner Contest 152 Kiroku (python)
[Professional competition] I tried At Coder Beginner Contest 175 (A ~ C)
[At Coder] ABC085C --Otoshidama's Python answer
AtCoder Beginner Contest 174 C Problem (Python)
Solve AtCoder Beginner Contest 170 D --Not Divisible (ABC170D) with python (Eratosthenes sieve)
At Coder (2020/09/08)
[Python] ABC133B (upper right triangle problem) [At Coder]
AtCoder Beginner Contest 169, D. Div Game short code
Solve A ~ D of yuki coder 247 with python
[Python] ABC159D (High School Mathematics nCr) [At Coder]
Solve AtCoder Beginner Contest159 D --Banned K (ABC159D) with python (count is too slow!)