1971.md

1971. Find if Path Exists in Graph

Solution 1 (time O(n), space O(n))

class Solution(object):
    def validPath(self, n, edges, source, destination):
        """
        :type n: int
        :type edges: List[List[int]]
        :type source: int
        :type destination: int
        :rtype: bool
        """
        g = collections.defaultdict(list)
        for n1, n2 in edges:
            g[n1].append(n2)
            g[n2].append(n1)
        q = deque()
        vis = set()
        q.append(source)
        vis.add(source)
        while q:
            cur_node = q.popleft()
            if cur_node == destination:
                return True
            for new_node in g[cur_node]:
                if new_node in vis:
                    continue
                q.append(new_node)
                vis.add(new_node)
        return False