Click here to see the full article post
I think, the fact that we are given an adjacency matrix, the time complexity is O(N^2), even using DFS or BFS
For the union-find complexity analysis: If we traverse over the complete matrix O(n^2) and union/find operations take O(n), wouldn't the complexity be O(n^3)?
@sean46 It depends of your union/find implementation.A efficient one with rank and path compression, will give you O(1) on average.
I think for Union-Find approach, the complexity could be O(n^2) if path compression is used. Union-Find complexity with path compression is O(m), which m is operations (either union/find); in this case, since m[i][j] = m[j][i], the union operation is at most n*(n-1)/2, therefore it is O(n^2)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.