[LeetCode] 1971. Find if Path Exists in Graph

- Problem

1971. Find if Path Exists in Graph

- BFS

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def bfs(x):
            q = collections.deque([x])
            visited = [False] * n
            visited[x] = True

            
            while q:
                x = q.popleft()
                if x == destination:
                    return True

                for i in graph[x]:
                    if not visited[i]:
                        q.append(i)
                        visited[i] = True
            
            return False
        
        graph = [[] for _ in range(n)]

        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        
        return bfs(source)

- Union find

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def find(x: int) -> int:
            try:
                if x != parents[x]:
                    x = find(parents[x])
                return x
            except:
                return None

        def union(x: int, y: int) -> None:
            x, y = map(find, (x, y))
            if x < y:
                parents[y] = x
                return
            parents[x] = y

        parents = [i for i in range(n)]
        
        for s, e in edges:
            union(s, e)

        return find(parents[source]) == find(parents[destination])

        return False

- Union Find (Refactored)

- 결과