My algorithm :
1. Create a 2D array a[n][n] where a[i][j] = No. of paths poissible
from i to j .
2. Initialize all elements of a[][] to zero.
3. For each vertex i from 1 to N
(a) Read the list of vertices it is connected to. For each
vertex V in the list increment a[i][V].
(b) For all
I think your algorithm will not always correctly join the paths.
Take a simple example
1->[2]
2->[3]
3->[]
You will increment a[1][2]
then a[2][3], then a[1][3]
But if the rows were the other way around:
1->[]
2->[1]
3->[2]
You will increment a[2][1]
Then a[3][2], but you won't increment a[3]
Take the following input:
3
0
1 1
2 1 2
2 extends 1, 3 extends 1 and 2, which represents a diamond dependency
(well, more a triangular one, but it still counts for this problem).
If I'm understanding your algorithm correctly, then after 3a, your array
would be:
0 0 0
1 0 0
1 1 0
As there is
