[LeetCode/Python/Disjoint Sets] 6/25 Redundant Connection 풀이

공부한 내용 - 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가 얼마나 있는지 알아야 함.

    2) Collapsing rule

    - Node j가 i에서 i의 root로 가는 path이고, parent[i] ≠ root(i)라면, parent[j]는 root(i)로 둘 수 있다.

    - 하나를 찾을 땐 시간이 많이 걸리게 하지만, 연속 찾기에선 worst case time을 줄여준다.

---

문제 - Rudundant Connection(불필요한 연결)

https://leetcode.com/problems/redundant-connection/

Redundant Connection - LeetCode

 1. Summary

  방향성이 없는 연결된 graph가 있다. 하나는 불필요하게 이어져 있어서, 지워도 되는 edge를 찾아라!

 

2. 풀이 - Union-Find를 배열로 풀이

  https://leetcode.com/problems/redundant-connection/solution/

Redundant Connection - LeetCode

edges 안 edge를 반복문으로 돌면서, parent가 같으면 return 함.

그렇지 않으면 parent와 Rank를 Update해준다.