I have a graph represented by a dictionary with this values:
self.dicpre: {0: [1, 2], 1: [2]}
What the dicpre is representing is that node 0 has two children (node 1 and 2), and node 1 has one children (node 2).
I'm using a recursive function to check if there is a close-loop (direction matters in this case) based on DFS. For doing that, I'm using a vector need to check if I visited that node before. If I start with the vector with all zeros:
need = [0]*numNodes
and I call the recursive fuction:
self.doCourse(node,need)
The fuction is like this:
def doCourse(self, node: int, need: List[int]) -> bool:
if need[node] == 1:
return False
else:
need[node] = 1
if node in self.dicpre:
for c in self.dicpre[node]:
if not self.doCourse(c,need):
return False
return True
So first I visit node 0 then node 1 (children from 0) and then node 2 (children from 1). Because node 2 have no children, I come back to node 0 and visit its other children which is node 2 again. What I expected to see for each call to the fuction would be:
1- For Node 0, need = [1,0,0]
2- For Node 1, need = [1,1,0]
3- For Node 2, need = [1,1,1]
4- Come back to the Node 0 call (and then need whould be reset) and visit Node 2 again so need = [1,0,1]
However, when I come back to the node 0 to visit node 2, the need vector is not reset and I have:
Node 0, need = [1, 0, 0]
Node 1, need =[1, 1, 0]
Node 2, need =[1, 1, 1]
Node 2, need = [1, 1, 1]
I thought that when you call a recursive function, you stack all the variables in memory, but this is not the case because the vector need does not return to its original value.
Am I missunderstanding something here? Thanks a lot
