Click here to see the full article post
I think the time complexity for the union-find not by rank method is not right. the first loop to construct dsu calls union O(P) times and union runs in O(logP) time because it called find. So the overall should be O( (N+P)log P )?
I think the time complexity of DFS method is not right
The time complexity of DFS is O(|V| + |E|), and here, |V| = N, and |E| = P. The DFS is executed "N" times, so then shouldn't the time complexity be O(N(N + P)) ?
Hi, I agree with the time complexity of DFS method is O(N + P), what do you think? @awice
This union operation is not weighted, so the time complexity won't be logP, it could be P?
@wwan I agree with you
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.