DSU(Disjoint Set Union)

• DSU(Disjoint Set Union)

  • 교집합이 없는 두개의 집합(서로소)을 하나로 합치는 작업을 한다.

  • 왜 필요한가?

    • n이 10 ** 5 개인 그래프에서 단순 BFS나 DFS로 호출할 경우 모든 경로를 찾기 위해서는 n개인 10 ** 5번의 작업이 필요하다.
    • 한 개를 찾을 경우 BFS나 DFS로 충분하지만 만약 e가 10 ** 5개를 찾아야 한다면 10 ** 10(10 ** 5 * 10 ** 5)번을 해야하며 시간초과가 나게 된다.
    • 그렇기에 한번의 작업을 할때마다 parent를 업데이트해주는 DSU를 사용하면 해결할 수 있다.

  • 시간복잡도

    • O(NlogN + ElogE + N + E)

• 구현

  • 초기화

      def __init__(self, n):
          self.parent = [i for i in range(n)]
          self.size = [1] * n

    • self.parent : 자신의 루트 원소. 즉, 집합의 최상단을 의미한다. 처음에는 자기자신이 집합의 루트이다.
    • self.size : 자신이 속한 집합의 사이즈, 처음에는 자기자신만 있기때문에 1이다.

  • find함수

      def find(self, u):
          if self.parent[u] == u:
              return u
          self.parent[u] = self.find(self.parent[u])
          return self.parent[u]

    • 현재 자신이 속한 집합의 최상단 루트를 리턴하는 함수이다.
    • self.parent[u] = self.find(self.parent[u])를 함으로써 집합의 트리를 평평하게 만들어 준다.
    • 최하단에 있는 원소도 리턴받은 루트를 적용시키는 작업을 했기 때문이다.

      • union함수

        def union(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.size[u] > self.size[v]:
            self.parent[v] = u
            self.size[u] += self.size[v]
        else:
            self.parent[u] = v
            self.size[v] += self.size[u]

    • u와 v의 parent를 찾고 만약 같다면 같은 집합에 있기 때문에 집합을 합치는 작업이 필요없다.
    • 만약 parent가 다르다면 두개의 집합을 합치는 작업이 필요하다
    • 두개의 집합 중 사이즈가 큰(원소의 개수를 많이 가진 집합)집합이 parent가 되게 만드는 작업이다.

---

• 전체 코드

    class DSU:
        def __init__(self, n):
            self.parent = [i for i in range(n)]
            self.size = [1] * n
  
        def find(self, u):
            if self.parent[u] == u:
                return u
            self.parent[u] = self.find(self.parent[u])
            return self.parent[u]
  
        def union(self, u, v):
            u = self.find(u)
            v = self.find(v)
            if u == v:
                return
            if self.size[u] > self.size[v]:
                self.parent[v] = u
                self.size[u] += self.size[v]
            else:
                self.parent[u] = v
                self.size[v] += self.size[u]
  

문제 : 1697. Checking Existence of Edge Length Limited Paths

참고 : https://leetcode.com/discuss/general-discussion/1072418/Disjoint-Set-Union-(DSU)Union-Find-A-Complete-Guide