Story

Original Link written in korean

Frodo, a backcountry explorer, came to explore an underground cave with n rooms during his expedition. All rooms are numbered 0 through n-1. There are many, the only entrances are connected with 0 rooms.

Each room is connected to each other by passages that allow passage in both directions, but there is only one passage directly connecting the two different rooms. There is only one shortest path between any two different rooms, and there is no case where it is impossible to move between any two rooms.

Having obtained a map of this underground cave prior to his expedition, Frodo planned his expedition as follows:

1. You must visit every room at least once.

2. Certain rooms must be visited first before visiting.
   2.1. This means that you must visit Room B before visiting Room A.
   2.2. There is no or only one room that must be visited first in order to visit a room.
   2.3. For two or more different rooms, there is never the same room that must be visited first.
   2.4 A room is not a room that must be visited first and a room that must be visited later.

Among the above plans, 2.2, 2.3 and 2.4 mean that the pair of two rooms that must be visited in order is unique in the form of A → B (visit A ​​first and then B). In other words, Frodo made a visit plan so that the order of visit would not be arranged as follows.

• A → B, A → C (visit order order = […,[A,B],…,[A,C],…]) The room to visit after visiting A is B Two or more with and C
• The room to visit before visiting A in the form X → A, Z → A (visit order order = […,[X,A],…,[Z,A],…]) Two or more with X and Z
• A → B → C (visit order arrangement order = […,[A,B],…,[B,C],…), like B, after visit A ​​and before visit C at the same time

Also, you do not have to visit the room you need to visit first and the room you will visit later, so you can visit room A and then visit another room and then visit room B.

When the number of rooms n, a two-dimensional array path containing the number of two rooms connected by each of the corridors in the cave, and a two-dimensional array order containing the visit order set by Frodo are given as parameters, Frodo can explore all rooms according to the rules. Complete the solution function to return whether it exists.

It’s source is kakao intern coding test.

I/O example:

so the light colored rooms should be visited first to visit dark colored rooms

n path order —> result

9,[[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]],[[8,5],[6,7],[4,1]] —>true

question

**this is my code. I used stack. And when frodo arrived at room A, room needed to visit first, to visit Room B, then I added rooms on dictionary that can only be accessed after arriving Room B.
so to explain my code briefly, in dictionary value B does not exist. value B is added after arriving room A

It could have some errors, but I/O case correct rate was about 0.95/1**

#adding key B in dictionary
def check(a,route,res,path):
    if a in res:
        p=res[a]
        del[res[a]]
        if a not in res:
                for c in path:
                    if p in c:
                        for j in c:
                            if j!=p :
                                if j in route:
                                    if p not in route[j]:
                                        route[j].append(p)
                                else:
                                    route[j]=[p]
    return None
def solution(n, path, order):
    res=dict(order)
    #making order library
    warn=[]
    for i in order:
        if i[1] not in warn:
            warn.append(i[1])
    route={}
    #making connected library except B values. so if value does not exist in library. frodo can not reach room B
    for i in range(n):
        for j in path:
            if i in j:
                for k in j:
                    if k in warn or i==k:
                        pass
                    else:
                        if i in route:
                            route[i].append(k)
                        else:
                            route[i]=[k]
    for j in range(len(order)):
        #repeated because there are len(order) B rooms.
        stack=[]
        visited=set()
        stack.append(0)
        visited.add(0)
        while len(stack)!=0:
            a=stack.pop()
            visited.add(a)
            check(a,route,res,path)
            if a in route:
                for i in route[a]:
                    if i not in visited:
                        stack.append(i)
            #so visited room number should be same with n. it means that all rooms are visited
            if len(visited)==n:
                return True
    return False