compcodingisnorealskill's blog

By compcodingisnorealskill, history, 5 years ago, In English

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