Topological Sort using BFS(Kahn's algorithm)

"""
Intuition for Kahn's Algorithm (BFS-based Topological Sort)

Step 1: Identify the Problem Type
---------------------------------
Topological Sort is a linear ordering of vertices such that for every
directed edge u -> v, node u comes before v. This is only possible in
a Directed Acyclic Graph (DAG). Since we want to solve this using BFS
(level-by-level processing), we use Kahn's Algorithm.

Step 2: The Core Concept (In-Degree)
------------------------------------
In BFS, we usually start from a 'source'. In a DAG, a logical starting
point is a node that has NO dependencies.
- In-Degree: The number of incoming edges to a node.
- If In-Degree == 0: No other node needs to come before this one.
  It can safely be placed at the beginning of our ordering.

Step 3: Initializing the Process
--------------------------------
1. Calculate the In-Degree of all nodes by traversing the adjacency list.
2. Find all nodes with In-Degree 0 and push them into a Queue.
   - These are our 'starting' nodes.

Step 4: The 'Removal' Logic (The BFS Loop)
------------------------------------------
While the Queue is not empty:
1. Pop a node 'u' from the Queue and add it to the Topological Sort result.
2. For every adjacent node 'v' (where an edge u -> v exists):
   - 'Virtually' remove the edge u -> v.
   - Since node 'u' is now placed in the ordering, node 'v' has one
     fewer dependency.
   - Decrease the In-Degree of node 'v' by 1.

Step 5: Activating New Nodes
----------------------------
After decreasing the In-Degree of node 'v', check:
- If In-Degree of 'v' becomes 0: All its dependencies have been placed
  in the ordering.
- Push node 'v' into the Queue so it can be processed next.

Step 6: Final Result
--------------------
Once the Queue is empty, the nodes in our result list are in
Topological Order.
- Note: If the result list contains fewer than 'V' nodes, the graph
  must have a cycle (Topological Sort is impossible).

Step 7: Complexity
------------------
- Time: O(V + E) - We visit every node and every edge once.
- Space: O(V) - To store the In-Degrees and the Queue.
"""
from collections import defaultdict
class Solution:
    def topoSort(self, v, edges):
        adj=defaultdict(list)
        indegree=[0]*v
        for a,b in edges:
            adj[a].append(b)
            indegree[b]+=1
        st=[]
        for i in range(v):
            if indegree[i]==0:
                st.append(i)

        ans=[]
        while st: #visited is not needed here because once the indegree of a node is 0 and you again go to that node, it will make it -1
            temp=st.pop()
            ans.append(temp)
            for neigh in adj[temp]:
                indegree[neigh]-=1
                if indegree[neigh]==0:
                    st.append(neigh)
        return ans