Calculate number of nodes between two vertices in an acyclic Graph by DFS method | Function to return the count of nodes in the path from source to destination ; Mark the node visited ; If dest is reached ; Traverse all adjacent nodes ; If not already visited ; If there is path , then include the current node ; Return 0 if there is no path between src and dest through the current node ; Function to return the count of nodes between two given vertices of the acyclic Graph ; Initialize an adjacency list ; Populate the edges in the list ; Mark all the nodes as not visited ; Count nodes in the path from src to dest ; Return the nodes between src and dest ; Driver Code ; Given number of vertices and edges ; Given source and destination vertices ; Given edges
def dfs ( src , dest , vis , adj ) : NEW_LINE INDENT vis [ src ] = 1 NEW_LINE if ( src == dest ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT for u in adj [ src ] : NEW_LINE INDENT if not vis [ u ] : NEW_LINE INDENT temp = dfs ( u , dest , vis , adj ) NEW_LINE if ( temp != 0 ) : NEW_LINE INDENT return temp + 1 NEW_LINE DEDENT DEDENT DEDENT return 0 NEW_LINE DEDENT def countNodes ( V , E , src , dest , edges ) : NEW_LINE INDENT adj = [ [ ] for i in range ( V + 1 ) ] NEW_LINE for i in range ( E ) : NEW_LINE INDENT adj [ edges [ i ] [ 0 ] ] . append ( edges [ i ] [ 1 ] ) NEW_LINE adj [ edges [ i ] [ 1 ] ] . append ( edges [ i ] [ 0 ] ) NEW_LINE DEDENT vis = [ 0 ] * ( V + 1 ) NEW_LINE count = dfs ( src , dest , vis , adj ) NEW_LINE return count - 2 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT V = 8 NEW_LINE E = 7 NEW_LINE src = 5 NEW_LINE dest = 2 NEW_LINE edges = [ [ 1 , 4 ] , [ 4 , 5 ] , [ 4 , 2 ] , [ 2 , 6 ] , [ 6 , 3 ] , [ 2 , 7 ] , [ 3 , 8 ] ] NEW_LINE print ( countNodes ( V , E , src , dest , edges ) ) NEW_LINE DEDENT