Hi everyone, I’m trying to solve problem in which I have to calculate the number of paths from one node to all of other nodes in the directed graph and I have a predetermined length of paths. The problem can be solved by simple recursive function, but the size of the input data precludes this option. Connections between two nodes which appear at the input, can appear more then once and we treat them as a different connections.

Code:

N, M, K (1<=N<=40, 1<=M<=100000, 1<K=10^1000), where n is number of nodes, m is number of connections and k is length of paths.

Example:

Code:

Input:
4 6 2
1 2
2 1
1 1
1 2
2 4
1 3
Output:
3
2
1
2
Explanation:
All possible paths with 2 hops are: (1,1,1), (1,2,1), (1,2,1), (1,1,2), (1,1,2), (1,1,3), (1,2,4), (1,2,4).

The fact is that the number of vertices is very small relative to the number of connections, so in the graph will be many hundreds of cycles. I wonder if somehow can use this fact.

Please, help me.