Implementing Kosaraju's algorithm to detect a cycle in a list of edges

Question

I'm going off the pseudo code in this link but I can't seem to get it working to detect the SCCs or any cycles. Trying to detect cycles in a list of edges Any help is appreciated.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if len(prerequisites) == 0:
            return True
            
        adj = defaultdict(list)
        inv = defaultdict(list)
        for i, j in prerequisites:
            if i ==j: return False
            adj[j].append(i)
            inv[i].append(j)
        
        topo = []
        visited = set()
        def toposort(head):
            if head in visited: return
            visited.add(head)
            for neighbor in adj[head]:
                toposort(head)
            topo.append(head)
        
        for i in range(numCourses):
            toposort(i)

        assigned = set()
        scc = defaultdict(list)

        def kos(u, root):
            if u in assigned: return
            assigned.add(u)
            scc[root].append(u)
            for neighbor in inv[u]:
                kos(neighbor, root)
        
        for i in reversed(topo):
            kos(i, i)
        print(scc)
        return max(len(v) for v in scc.values()) <= 1

Answer 1

In your topological sort, inside the loop, you should pass the neighbor as an argument to toposort, not the current head node. Also, kos is not correctly traversing the graph in reverse order, it should be iterating over the neighbors of u in inv[u], it is calling kos(neighbor, root) recursively with the same u parameter. Here's the code:

Playground Link:

from collections import defaultdict
from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if len(prerequisites) == 0:
            return True
            
        adj = defaultdict(list)
        inv = defaultdict(list)
        for i, j in prerequisites:
            if i == j:
                return False
            adj[j].append(i)
            inv[i].append(j)
        
        topo = []
        visited = set()
        def toposort(head):
            if head in visited:
                return
            visited.add(head)
            for neighbor in adj[head]:
                toposort(neighbor)
            topo.append(head)
        
        for i in range(numCourses):
            toposort(i)

        assigned = set()
        scc = defaultdict(list)

        def kos(u, root):
            if u in assigned:
                return
            assigned.add(u)
            scc[root].append(u)
            for neighbor in inv[u]:
                kos(neighbor, root)
        
        for i in reversed(topo):
            if i not in assigned:
                kos(i, i)

        for component in scc.values():
            if len(component) > 1:
                return False

        return True
        
solution = Solution()
print(solution.canFinish(2, [[1,0]])) # True
print(solution.canFinish(2, [[1,0],[0,1]])) # False

print(solution.canFinish(3, [[0,1],[0,2],[1,2]])) # True
print(solution.canFinish(3, [[0,1],[1,2]])) # True

print(solution.canFinish(4, [[1,0],[2,1],[3,2],[1, 3]])) # False
print(solution.canFinish(4, [[1,0],[2,1],[3,2],[3, 1]])) # True