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 a bath from 2 to 1, 3 to 1 and 3 to 2.
Iterating through (b), we see:
i = 1, nothing happens (there is no vertex < 1)
i = 2, there is no path from 1 to 2, so nothing happens
i = 3, there is no path from 1 to 3 or from 2 to 3, so nothing happens
Now if you had set both a[i][V] and a[V][i] to 1 in step (a), then it
will probably have worked. Alternatively, if you had checked as well
for a path from 2 to 1, that also would probably have worked.
I think you made the assumption that an edge of this graph will always
be directed from one number to a larger one, which was not necessarily
the case.
Cheers,
--Joe
Joe Collins
joe.collins...@gmail.com
On 07/05/12 20:04, abcstdio wrote:
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 previous vertices j from 1 to i-1, if there is
already a path from j to i, then there must be a path from j to V via
i, so a[j][V]++.
If a[j][V]>1 then we have got the answer, so simply read
the rest of the input and no need of any computations.
It gave me Wrong Answer on the small input test. Please point out the
errors.
--
You received this message because you are subscribed to the Google Groups "Google
Code Jam" group.
To post to this group, send email to google-code@googlegroups.com.
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
