Union Find
-
[LeetCode/Python/Disjoint Sets] 6/25 Redundant Connection 풀이프로그래밍/LeetCode 2021. 6. 26. 12:01
공부한 내용 - Disjoint Sets (Union-Find) 1. Disjoint Sets란? - Si, Sj 두 Sets가 있을 때, Si와 Sj에 같은 element가 존재하지 않는 Sets (i ≠ j) - 서로 중복되는 element가 없는 Sets 2. Operation 1) Union(i, j) - Si, Sj가 Disjoint Sets라면, Si U Sj = {all element x, x는 Si or Sj의 element} 2) Find(i) - element i가 포함된 Set를 찾음 3. Union의 Rule 1) Weighting rule - tree i의 node개수가 tree j의 node개수보다 작으면, j를 i의 부모로 만든다. - tree마다 node가 얼마나 있는지 알아..