Number of paths from source to destination in a directed acyclic graph | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  1000005 NEW_LINE vector < int > v [ MAXN ] ; void add_edge ( int a , int b , int fre [ ] ) { v [ a ] . push_back ( b ) ; fre [ b ] ++ ; } vector < int > topological_sorting ( int fre [ ] , int n ) { queue < int > q ; for ( int i = 0 ; i < n ; i ++ ) if ( ! fre [ i ] ) q . push ( i ) ; vector < int > l ; while ( ! q . empty ( ) ) { int u = q . front ( ) ; q . pop ( ) ; l . push_back ( u ) ; for ( int i = 0 ; i < v [ u ] . size ( ) ; i ++ ) { fre [ v [ u ] [ i ] ] -- ; if ( ! fre [ v [ u ] [ i ] ] ) q . push ( v [ u ] [ i ] ) ; } } return l ; } int numberofPaths ( int source , int destination , int n , int fre [ ] ) { vector < int > s = topological_sorting ( fre , n ) ; int dp [ n ] = { 0 } ; dp [ destination ] = 1 ; for ( int i = s . size ( ) - 1 ; i >= 0 ; i -- ) { for ( int j = 0 ; j < v [ s [ i ] ] . size ( ) ; j ++ ) { dp [ s [ i ] ] += dp [ v [ s [ i ] ] [ j ] ] ; } } return dp ; } int main ( ) { int n = 5 ; int source = 0 , destination = 4 ; int fre [ n ] = { 0 } ; add_edge ( 0 , 1 , fre ) ; add_edge ( 0 , 2 , fre ) ; add_edge ( 0 , 3 , fre ) ; add_edge ( 0 , 4 , fre ) ; add_edge ( 2 , 3 , fre ) ; add_edge ( 3 , 4 , fre ) ; cout << numberofPaths ( source , destination , n , fre ) ; }