Disjoint Set Union and Find

Revision en1, by compcodingisnorealskill, 2019-08-31 10:11:03

Hello,

Today I learned about DSU or Disjoint set union. Disjoint is basically when two sets have intersection == NULL. This is a powerful tool for : 1) Finding Cycles 2) Checking if two elements are in same group or not i.e linked by some logic together

Two really good questions for these are : 1167C - News Distribution and for cycles it is 1205B - Shortest Cycle

The main logic is to implement two functions 1) Find and 2) Union and then keep representatives of the set together.

Good luck! This tutorial on topcoder is good too Link to DSU

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English compcodingisnorealskill 2019-08-31 10:11:03 673 Initial revision (published)