topological sort template

https://freedeveloper.tistory.com/390

This explains well but basically it is for DAG (directed so has direction). We put all nodes with indegree 0 in the queue and traverse their children nodes and minus their indegrees in the process. If their indegrees are subtracted to value 0, only then we add them to our queue to be traversed.

This sort is used for calculating reachability or determining the order in which elements should be arranged.

Example v impt

https://leetcode.com/problems/course-schedule/submissions/1563497062/?envType=problem-list-v2&envId=7p5x763&sorting=W3sic29ydE9yZGVyIjoiREVTQ0VORElORyIsIm9yZGVyQnkiOiJGUkVRVUVOQ1kifV0%3D&page=1

Lets say we have to take a pre-course before we can take this particular course. So it si

0,1 format.
pre -> course
1 -> 0

impt notes!!
1) the indegree of course increases by 1
2) graph[pre].append(course)

2) i get confused what to add so i think is b->a so graph[a].append(b) (wrong) but is it other way round. it just depends on the arrow.

if a->b, graph[a].append(b)

if b->a like this case, graph[b].append(a)

like think logically, for a->b case if we finished traversing a for example, its neighbour b's indegree will be decremented and if its indegree is 0, we add that to queue. Its not the other way round .

especially is confusing but lets say we have example of
2 → 1 → 0. The correct graph should look like graph = [[], [0], [1]] # 2 → 1 → 0

When building an Adjacency List for this problem, you want to store the next courses you can take after completing a prerequisite.

another mistake

Becareful not to reuse variable name like n or p. I took n as length of input but i reused n for other parts like neighbour in graph[node] as n. This causes mistake

from collections import deque
class Solution:
    def canFinish(self, n: int, pre: List[List[int]]) -> bool:
        queue =deque()
        graph=[[] for _ in range(n)]
        indegree=[0 for _ in range(n)]
        for course, prerequisite in pre: #correct unpacking
            graph[prerequisite].append(course)
            indegree[course] += 1
        
        for i in range(n):
            if indegree[i]==0:
                queue.append(i)
        count=0
        while queue:
            count+=1
            node = queue.popleft()
            for neigh in graph[node]:
                indegree[neigh]-=1
                if indegree[neigh]==0:
                    queue.append(neigh)
        return count==n

complexity

v+e time cuz:
building graph -> E (pre length)
check all n nodes -> V (n)
so this bfs traversal processes each node and edge (v+e)

v+e space cuz
graph stores v+e, which is adjacency list of vertices and edges