Why is this code not terminating and going on for infinite loop?-CodePudding

This is my attempt at solving Leetcode's Question no 841 What I have done is, I made an array dp which has the size of len(rooms) and all are intially 0. Then I set dp[0] to be 1. The I made dequeu called queue and appended the first room that he can go. From there which ever room keys he has he goes there marking dp[k]=1 and once when all possible ways are over the queue should be empty and I should end up with the ans.

But when I run this code it showed me TLE error hence I added the print statements to debug and then the output is something that is beyond my understanding. I know I can get solutions in discuss section but I want to what I have done wrong here.

Here is the code:-

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n=len(rooms)
        dp=[0]*n
        dp[0]=1
        print(dp)
        queue=deque()
        queue.append(rooms[0])
        while queue:
            print(queue)
            i=queue.popleft()
            for k in i:
                dp[k]=1
                queue.append(rooms[k])
        if 0 in dp:
            return False
        else:
            return True

CodePudding user response：

Oh God! The problem that was happening here was that when ever I encourtered a room I was appending it to the queue so, that room took me to some other room and like that this kept on going hence the infinite loop.

Just 1 small correction and it worked Here is the code:

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n=len(rooms)
        dp=[0]*n
        dp[0]=1
        # print(dp)
        queue=deque()
        queue.append(rooms[0])
        while queue:
            # print(queue)
            i=queue.popleft()
            for k in i:
                if not dp[k]:
                    dp[k]=1
                    queue.append(rooms[k])
        if 0 in dp:
            return False
        else:
            return True

CodePudding user response：

Because inside while loop you are keep on increasing queue by code used queue.append(rooms[k]) so in every loop when it goes to while queue: it will have the new element you appended (rooms[k]). You can put some condition to before appending queue or some exit condition from the loop.