DSU/Union-Find

Revision en1, by Sahilamin219, 2020-11-19 15:30:06

I was solving some DSU question and i m not able to understand when should we do path compression and when not . For example like in these two questions .

1.Redundant Connection

Solution 1

2.Redundant Connection II

Solution 2

For better idea of solution 2 visit

As you can see in 2nd question while finding cycle we are not doing path compression. If anyone can explain the concept behind this it would be very helpful.

Tags #dsu, #advice

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Sahilamin219 2020-11-19 15:30:06 2481 Initial revision (published)