Why is this throwing this error: local variable 'visited' referenced before assignment in Python 3 on Leetcode?

Question

I'm able to reference the other variables like preReq and taken without issue, but when trying to access visited, I am told I'm referencing the variable before its assignment. Am I missing something with scope that the other variable assignments have that visited does not?

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        preReqs = {}
        taken = [0] * numCourses
        visited = []
        for course in range(numCourses):
            preReqs[course] = []
        
        for prereq in prerequisites:
            preReqs[prereq[0]].append(prereq[1])
            
        def dfs(course):
            print(visited[0])
            if course in visited:
                return False
            else:
                visited.append(course)
            
            for preReq in preReqs[course]:
                if taken[preReq] == 1:
                    preReqs[course].remove(preReq)
                else:
                    dfs(preReq)
            if preReqs[course] == []:
                taken[course] = 1
                visited = []
            
        for each in range(numCourses):
            dfs(each)
    
        for each in taken:
            if each == 0:
                return False
        return True

Welcome to Stack Overflow. Please read [ask] and the [formatting help](https://stackoverflow.com/help/formatting), and make sure your code appears here with the same indentation as the actual code, since indentation is crucial in Python. As it stands, it's impossible to be sure about the variable scope in this code. Please also read [mre], and show a [complete](https://meta.stackoverflow.com/questions/359146/) error message, by copying and pasting, starting from the line that says `Traceback (most recent call last):`, and formatting it like code. — Karl Knechtel, May 29 '22 at 02:36
@Nick It seems to throw the issue even if I comment out everything and only print the value of visited, so it doesn't seem like it's an assignment issue. — Andrew Wang, May 29 '22 at 03:31
@AndrewWang please [edit] the question to show the minimal code which demonstrates the problem — Nick, May 29 '22 at 03:36
@Nick Should be edited now. Sorry about that. I think the main problem for me is understanding why visited and taken are treated differently in dfs() — Andrew Wang, May 29 '22 at 04:28
Thank you for editing the code. Looks like it matches what I thought was most likely. The difference is that `visited` is *assigned to*, whereas `taken` isn't - the *value* named *taken* is merely *modified*. Assignment to a variable anywhere in a function makes it a local *at compile time*, unless otherwise specified. Here, the desired `visited` isn't global, but it also isn't local - it's what Python calls `nonlocal`, and that is the keyword needed to access it. — Karl Knechtel, May 29 '22 at 16:21

Drew Bermudez · Answer 1 · 2022-05-29T02:30:50.153

prerequisites and the other variables that work are taken in as function variables, whereas the other variables that it cannot access (visited in your example) are declared within your nested function dfs.

It's generally bad practice to nest a function like this. I went ahead and rewrote your class so you can see how to make it a bit easier on yourself. Note that you could make this tidier initializing variables in an __init__(self) function.

class Solution:

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        self.preReqs = {}
        taken = [0] * numCourses
        self.visited = []
        for course in range(numCourses):
            self.preReqs[course] = []
            
        for prereq in prerequisites:
            self.preReqs[prereq[0]].append(prereq[1])
                
        for each in range(numCourses):
            self.dfs(each)
        
        for each in taken:
            if each == 0:
                return False
        return True

    def dfs(self,course):
            if course in self.visited:
                return False
            else:
                self.visited.append(course)
                
            for preReq in preReqs[course]:
                if taken[preReq] == 1:
                    preReqs[course].remove(preReq)
                else:
                    self.dfs(preReq)
            if preReqs[course] == []:
                taken[course] = 1
                self.visited = []

There's nothing particularly wrong with defining `dfs` as a closure. It just has to declare `visited` as a nonlocal variable if it plans on assigning to it. — chepner, May 29 '22 at 02:47

Why is this throwing this error: local variable 'visited' referenced before assignment in Python 3 on Leetcode?

1 Answers1