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][1], even though a path exists from 3 -> 1. Basically you are only extending the paths for vertices that are encountered in the correct order in the input file. Paul Smith [email protected] On Mon, May 7, 2012 at 8:04 PM, abcstdio <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
