Problem statement

https://leetcode.com/problems/all-paths-from-source-lead-to-destination/

Solution

What we need to do in this problem is to check if we need to check if we start from source node then we always end up in destination. We also need to check also that we do not have loops, which can be reached from source node. It can be done with usual dfs with 3 colors or we can keep visited set and add and delete nodes from it. Each time when we visit neibs, we need to check if not fully visited yet and if dfs(neib) is False, then we return False. If we did not return False, return True in the end.

Complexity

It is O(E+V) for time and space.

Code

class Solution:
    def leadsToDestination(self, n, edges, source, destination):
        G = defaultdict(list)
        for x, y in edges:
            G[x].append(y)

        visited = set()
        
        def dfs(node):
            if len(G[node]) == 0:
                return node == destination
            
            visited.add(node)
            for neib in G[node]:
                if neib in visited or not dfs(neib): return False
            visited.remove(node)
            return True

        return dfs(source)