# Leetcode 1971. Find if path exist in graph

[並查集詳解](https://zh.wikipedia.org/zh-tw/%E5%B9%B6%E6%9F%A5%E9%9B%86)

## Union Find

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def find(parent, x):
            if parent[x] != x:
                parent[x] = find(parent, parent[x])
            return parent[x]
        
        def union(parent, u, v):
            root_u = find(parent, u)
            root_v = find(parent, v)
            if root_u != root_v:
                parent[root_u] = root_v
            
        parent = [i for i in range(n)]

        for u, v in edges:
            union(parent, u , v)
        
        return find(parent, source) == find(parent, destination)

## DFS

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True
        neihbors = [[] for i in range(n)] # 列出所有節點的相鄰節點
        visited = [False for i in range(n)] # 標記已走訪
        for vi,vj in edges: # 插入相鄰節點
            neihbors[vi].append(vj)
            neihbors[vj].append(vi)
        
        stack = [source] # 把開始節點放入棧
        visited[source] = True # 標記開始節點已走訪
        while stack:
            current = stack.pop()
            ns = neihbors[current]
            if destination in ns: # 如果目的地已經存在於相鄰節點中
                return True
            else: # 沒有存在於相鄰節點中
                for n in ns: # 把所有相鄰節點入棧走訪
                    if not visited[n]: # 如果節點還未走訪過
                        stack.append(n)
                        visited[n] = True # 標記相鄰節點已經走訪，避免下次重複走訪
        return False # 都沒有找到目的地