Number of paths from source to destination in a directed acyclic graph | Python3 program for Number of paths from one vertex to another vertex in a Directed Acyclic Graph ; to make graph ; function to add edge in graph ; there is path from a to b . ; function to make topological sorting ; insert all vertices which don 't have any parent. ; using kahn 's algorithm  for topological sorting ; insert front element of queue to vector ; go through all it 's childs ; whenever the frequency is zero then add this vertex to queue . ; Function that returns the number of paths ; make topological sorting ; to store required answer . ; answer from destination to destination is 1. ; traverse in reverse order ; Driver code ; here vertices are numbered from 0 to n - 1. ; to count number of vertex which don 't  have any parents. ; to add all edges of graph ; Function that returns the number of paths
from collections import deque NEW_LINE MAXN = 1000005 NEW_LINE v = [ [ ] for i in range ( MAXN ) ] NEW_LINE def add_edge ( a , b , fre ) : NEW_LINE INDENT v [ a ] . append ( b ) NEW_LINE fre [ b ] += 1 NEW_LINE DEDENT def topological_sorting ( fre , n ) : NEW_LINE INDENT q = deque ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( not fre [ i ] ) : NEW_LINE INDENT q . append ( i ) NEW_LINE DEDENT DEDENT l = [ ] NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT u = q . popleft ( ) NEW_LINE l . append ( u ) NEW_LINE for i in range ( len ( v [ u ] ) ) : NEW_LINE INDENT fre [ v [ u ] [ i ] ] -= 1 NEW_LINE if ( not fre [ v [ u ] [ i ] ] ) : NEW_LINE INDENT q . append ( v [ u ] [ i ] ) NEW_LINE DEDENT DEDENT DEDENT return l NEW_LINE DEDENT def numberofPaths ( source , destination , n , fre ) : NEW_LINE INDENT s = topological_sorting ( fre , n ) NEW_LINE dp = [ 0 ] * n NEW_LINE dp [ destination ] = 1 NEW_LINE for i in range ( len ( s ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( len ( v [ s [ i ] ] ) ) : NEW_LINE INDENT dp [ s [ i ] ] += dp [ v [ s [ i ] ] [ j ] ] NEW_LINE DEDENT DEDENT return dp NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE source , destination = 0 , 4 NEW_LINE fre = [ 0 ] * n NEW_LINE add_edge ( 0 , 1 , fre ) NEW_LINE add_edge ( 0 , 2 , fre ) NEW_LINE add_edge ( 0 , 3 , fre ) NEW_LINE add_edge ( 0 , 4 , fre ) NEW_LINE add_edge ( 2 , 3 , fre ) NEW_LINE add_edge ( 3 , 4 , fre ) NEW_LINE print ( numberofPaths ( source , destination , n , fre ) ) NEW_LINE DEDENT