Disjoint Set Union and Find

Правка en1, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский compcodingisnorealskill 2019-08-31 10:11:03 673 Initial revision (published)