Count paths with k edges

#1

https://practice.geeksforgeeks.org/problems/possible-paths/0/

plz check my code it gives tle…whereas i am using dfs with o(v+e) time complexity…
plz tell the reason and correct the code

#2

Reply to this at the earliest

#3

why is no one replying???

#4

Consider the graph having cycle. Then at first u are visiting an unvisited node. When all nodes visited and i are marking all nodes visited as unvisited. then, again u will go the same node as it is marked unvisited.
So, it will go to infinite loop hence, giving tle.

#5

Try to think of a dp based solution where there are three states: 1. Source 2. Destination 3. Number of paths between source and destination and try to solve the problem.

#6

i am unable to think of dp solution…plz help

also help me to solve this problem
https://practice.geeksforgeeks.org/problems/possible-paths-between-2-vertices/0/

#7

Think of the dp solution in the following way:

#8

You can solve the next problem by just traversing the graph using dfs and if src==dest increment your answer by 1. Since, it is DAG so visited array is not required .

#9

No it can contain cycle in the next problem I am getting the…in that on doing DFS

#10

Oh! yes, it can contain cycle. So, u can first create a dp array in the same i just told and the answer should be the summation of dp[src][des][i] for all i belonging to edges.

#11

how to change the given code that you have provided …plz tell the changes in form of code
and how will we do this question if undirected graph is given???plz tell

#12

i got this code from succesful submissions on geeks
they have also performed simple dfs but their code is getting accepted whereas my dfs code shows tle…
plz check this one…and how is this one diff from my dfs code ??

#13

i was not able to understand the tle reason plz elaborate

plz reply at the earliest

#14

Plz reply at the earliest

#15

This code is also giving wrong answer. Try to apply the following function:

#16

Which code is giving wa ??plz tell clearly…the code that I had sent of somebody else was from the correct submit section I submit it again it give 100…
I have asked 3 other questions in this doubt as well…plz ans them…
and tell me why DFS give tle… properly…plz

#17

plz reply at the earleist…

#18

???plz reply ???

#19

plz reply…