Prerequisite Tasks

//checking for circle in directed graph
from collections import defaultdict
def dfs(node, graph, visited):
    if visited[node] == 1:  # currently in recursion stack → cycle
        return False
    if visited[node] == 2:  # already processed
        return True

    visited[node] = 1  # mark as visiting

    for neighbor in graph[node]:
        if not dfs(neighbor, graph, visited):
            return False

    visited[node] = 2  # mark as done
    return True


# Solution class
class Solution:
    def isPossible(self, n, p,pre):
        # Build adjacency list
        graph = defaultdict(list)
        for a, b in pre:
            graph[b].append(a)

        visited = [0] * n  # 0=unvisited, 1=visiting, 2=done

        # Run DFS for all nodes
        for i in range(n):
            if visited[i] == 0:
                if not dfs(i, graph, visited):
                    return False

        return True


'''Method 2-most optmised'''
from collections import deque, defaultdict

class Solution:
    def isPossible(self, n, p, arr):
        # Build adjacency list
        graph = defaultdict(list)
        indegree = [0] * n

        for a, b in arr:
            graph[b].append(a)
            indegree[a] += 1

        # Start with nodes that have indegree 0
        q = deque([i for i in range(n) if indegree[i] == 0])
        count = 0

        while q:
            node = q.popleft()
            count += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)

        # If count == n, all tasks can be completed
        return count == n