[LeetCode] 261. Graph Valid Tree

 전형적인 Union-Find를 활용하는 문제다. 다만 Cycle이 발생할 수 있기에 이 때(if px == py) false를 반환하는 조건만 추가해주고 Parent가 하나라도 다르다면 Tree가 두 개 이상 생기는 것이기에 false를 반환하면 된다.

class Solution:
    def find(self, p, x):
        if p[x] == x:
            return x
        return self.find(p, p[x])

    def union(self, p, x, y):
        x = self.find(p, x)
        y = self.find(p, y)
        if x < y:
            p[y] = x
        else:
            p[x] = y

    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        p = [i for i in range(n)]

        for i in range(len(edges)):
            px = self.find(p, edges[i][0])
            py = self.find(p, edges[i][1])
            if px == py:
                return False
            self.union(p, edges[i][0], edges[i][1])
        
        r = self.find(p, 0)
        for i in range(n):
            c = self.find(p, i)
            if c != r:
                return False
        
        return True