link to the problem is link. As far as i am concerned the answer to it is Union Find. I have implemented the Union Find Algorithm, it is successfully executing the given test cases but when put on judge runtime error(NZEC) shows up,i am stuck and cant figure out where the problem is,remember it is not showing Wrong Answer neither TLE.
link to my solution is here link.please HELP.
Looks like you will have array index out of bounds.
idi = range(n)
will construct an array of n integers, indexed from 0 to n - 1 (never mind the negative indexing for now)
For the problem, 1 <= x, y <= n
So, if either x or y is n, then connected(x, y) will invoke root with parameter value as n. Within root, the expression idi[x] with value of x equal to n, will throw index out of bounds error, resulting in the runtime error.
You could try initializing idi to range(n + 1), which will ensure that the references never get out of index.
well,thanks for pointing that out,but could you explain why idi=range(1,n+1)[1,2,3…n] did not work(i tried it after you answer,it again showed Runtime error) but idi=range(n+1)[0,1,2…n] did,although in the question island started from 1 and not 0.
range(1, n + 1) creates a list containing elements from 1 (including) to n + 1 (excluding). Still, there are only n elements. i.e., idi[0] is 1, idi[1] is 2, … and idi[n - 1] is n. There is no idi[n] in this list.
range(n + 1) creates the list that you actually want: idi[0] is 0, idi[1] is 1, idi[2] is 2, …, idi[n - 1] is n - 1, and idi[n] is n.
You could have still used range(1, n + 1). But, the actual indices valid for that list would be still 0 to n - 1, and you would need to take care of that in code. With range(n+1), you are basically having a useless idi[0], but the rest is useful.
You were really helpful, thanks a lot
1 Like
My pleasure.