Strongly connected components(Kosaraju Algorithm)

"""
Intuition:

We are given a directed graph and want to find groups of nodes such that every node
in the group can reach every other node. These groups are called strongly connected components.

The key observation is that if we collapse each strongly connected component into a single node,
the overall graph becomes a Directed Acyclic Graph. This means there is a clear directional flow
between components, even though inside each component there may be cycles.

If we try to directly run DFS and collect components, we may move from one component into another,
because edges between components are one-directional and can mislead the traversal.

To avoid this, we first perform a DFS and record nodes in the order of their finishing time.
A node is added after all nodes reachable from it are fully explored. This ensures that nodes
that lie deeper in the direction of edges get placed earlier, and nodes that act like entry points
to components get placed later.

This finishing order gives us a safe sequence to process nodes so that when we start exploring,
we do not accidentally jump across components.

Next, we reverse all the edges of the graph. This step flips the direction of connections between
components. Now, paths that were going outward from a component become incoming, effectively isolating
each strongly connected component.

Finally, we process nodes in decreasing order of their finishing time. For each node that has not yet
been visited in this phase, we perform a DFS on the reversed graph. Each such DFS traversal will stay
completely within one strongly connected component, because the reversed edges prevent it from leaking
into other components.

Every time we start a new DFS in this phase, it corresponds to discovering a new strongly connected component.

The total number of such DFS calls gives the number of strongly connected components in the graph.
T.C= O(V+E) as graph can be disconnected also
"""

from collections import defaultdict
def dfs(i,adj,visited,st): #once traversal is done, push the node in st
    visited[i]=True
    for neigh in adj[i]:
        if visited[neigh]==False:
            dfs(neigh,adj,visited,st)
    st.append(i)

class Solution:
    def kosaraju(self, v, edges):
        adj=defaultdict(list)
        for a,b in edges:
            adj[a].append(b)
        visited=[False]*v
        st=[]
        for i in range(v):
            if visited[i]==False:
                dfs(i,adj,visited,st)

        #Now reverse the edges
        rev_adj=defaultdict(list)
        for a,b in edges:
            rev_adj[b].append(a)
        visited=[False]*v
        dummy_st=[]
        count=0

        while st:
            temp=st.pop()
            if visited[temp]==False:
                dfs(temp,rev_adj,visited,dummy_st) #We are not gonna use this dummy st
                count+=1
        return count