And why is there no good data to stop this obvious force algorithm?
- using only path compression O(log(n))
- using only rank O(log(n))
- using both O(log^*(n))
Disjoint Set Union (Union Find) | HackerEarth
oops. was unaware of log*(n) function. Thanks!
This should be the best solution for beginners!
This one is O(log(n)) for each query.
Itās basically āpath compressionā I think. How can some data get TLE on it ?
brute force! No itās not.
I tried it with simple brutal force ,and time limit exceeded ā¦ I donāt even got a single point in this question ā¦
Although sample test case easily passed on my solution ā¦
Donāt cry. I donāt think you were using path compression. were you using it ?
He used it.
Congratulations for getting sample correctš.
Yes, I found that I was wrong. In fact, it made up for my knowledge gap.
So loopfree == freeloop ?
Guys, do try the bonus problem from the editorial. It has a nice solution, but it fails DSU with path compression.
Yes, I havenāt practiced algorithmic problems for a long time, so Iām going to start over.
i think i need to study alot .
Yes, I found that I was wrong. In fact, I used a very silly algorithm.
Can you explain your solution?
My code was also similar but getting TLE in java
I have stopped crying now because I realised he also used path compression. Thanks dude, appreciate it.
I just made a vector hash of all the indices that were set to 0, and checked in the query of type 2 if the largest index in the subset was 0 or not. I realised though that vector is not the best of all hashes and I had to use Path Compression also.