Find whether it is possible to finish all tasks or not from given dependencies Using Python

code:

from collections import defaultdict

class graph:

    def __init__(self,v):

        self.v=v

        self.graph=defaultdict(list)

        

    def addEdge(self,u,v):

        self.graph[u].append(v)

        

    

        

    def isCycleUtil(self,visited,i,recStack):

        visited[i]=True

        recStack[i]=True

        

        for j in self.graph[i]:

            if visited[j]==False:

                if self.isCycleUtil(visited,j,recStack)==True:

                    return True

            elif recStack[j]==True:

                return True

                

        recStack[i]=False

        return False

        

    def isCycle(self):

        visited=[False]*self.v

        recStack=[False]*self.v

        

        for i in range(self.v):

            if visited[i]==False:

                if self.isCycleUtil(visited,i,recStack)==True:

                    return True

                    

        return False

        

    

    def find(self):

        if self.isCycle()==True:

            return False

            

        inDegree=[0]*(self.v+1)

        

        for i in self.graph:

            for j in self.graph[i]:

                inDegree[j]+=1

               

        

        

        done=[False]*(self.v+1)

        q=[]

        

        for k in range(self.v+1):

            if inDegree[k]==0:

                q.append(k)

                done[k]=True

        

        print(inDegree)

        while q:

            t=q.pop(0)

            

            for node in self.graph[t]:

                

                done[node]=True

                inDegree[node]-=1

                if inDegree[node]==0:

                    q.append(node)

            

            

        

        for p in done:

            if p==False:

                

                return False

        return True

                

                

#Driver Code               

g=graph(4)

g.addEdge(1,0)

g.addEdge(2,1)

g.addEdge(3,2)

print(g.find())

                    

Rat in a Maze Solution

code:

 def pathUtil(maze,visited,sol,x,y,N,possible):

    #print(sol)

    if x<0 or y<0 or x>N-1 or y>N-1 or maze[x][y]==0 or visited[x][y]==1:

        return

    

    if x==N-1 and y==N-1 and maze[x][y]==1:

        possible.append(sol)

        return

    

    visited[x][y]=1

    

    pathUtil(maze,visited,sol+'D',x+1,y,N,possible)

    pathUtil(maze,visited,sol+'U',x-1,y,N,possible)

    pathUtil(maze,visited,sol+'R',x,y+1,N,possible)

    pathUtil(maze,visited,sol+'L',x,y-1,N,possible)

    

    visited[x][y]=0

    

def path(maze,N):

    visited=[[0 for i in range(N)] for j in range(N)]

    sol=''

    possible=[]

    pathUtil(maze,visited,sol,0,0,N,possible)

    

    print("possible path : ",possible)

    

N = 4

maze = [[1, 0, 0, 0],

         [1, 1, 0, 1], 

         [1, 1, 0, 0],

         [0, 1, 1, 1]]

         

path(maze,N)