CareerCup

@Loler: would u mind to clarify how it's possible in O(logk) time? The adjacency matrix need to be multiplied O(logk) times, but that leads to O(n^3 logk) time in total. Plz correct me. Thanks.

k-th power of a matrix (A^k) can be found in O(log k) time (called repeated doubling). If A[u][v]==1 in A^k ,then there exist a path of length k between u and v. Thus, in O(log k) time we can tell whether the given two nodes are connected by a path length of k.

That's O(log k) /matrix multiplies/, which is not, in general, O(log k) time.

I agree. it's log k matrix multiplications which is not O(logk)time.

its log(k)*ncube

Exactly....that's wat i thought at first....
but it will only satisfy the second case.
For first case it will not O(1)...since we have to test ( find(u)==v or find(v)==u ),one of them will be O(1)...but other is definitely not.

Can you elaborate how would use union find for second case? Thanks

what if paths with different length exist between two nodes?

Then store all of them. You could use a linklist.