LeetCode: All Paths from Source Lead to Destination – Prepare For Coder Interview

All Paths from Source Lead to Destination

Similar Problems:

Given the edges of a directed graph, and two nodes source and destination of this graph, determine whether or not all paths starting from source eventually end at destination, that is:

At least one path exists from the source node to the destination node
If a path exists from the source node to a node with no outgoing edges, then that node is equal to destination.
The number of possible paths from source to destination is a finite number.

Return true if and only if all roads from source lead to destination.

Example 1:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false
Explanation: It is possible to reach and get stuck on both node 1 and node 2.

Example 2:

Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
Output: false
Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.

Example 3:

Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
Output: true

Example 4:

Input: n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2
Output: false
Explanation: All paths from the source node end at the destination node, but there are an infinite number of paths, such as 0-1-2, 0-1-1-2, 0-1-1-1-2, 0-1-1-1-1-2, and so on.

Example 5:

Input: n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1
Output: false
Explanation: There is infinite self-loop at destination node.

Note:

The given graph may have self loops and parallel edges.
The number of nodes n in the graph is between 1 and 10000
The number of edges in the graph is between 0 and 10000
0 <= edges.length <= 10000
edges[i].length == 2
0 <= source <= n – 1
0 <= destination <= n – 1

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

## https://code.dennyzhang.com/all-paths-from-source-lead-to-destination
## Basic Ideas: DFS
##
##  If there is a circle, return False
##  The last node should be destination
##  Need to deal with duplicate edges
##
## Complexity: Time ?, Space ?
class Solution(object):
    def leadsToDestination(self, n, edges, source, destination):
        """
        :type n: int
        :type edges: List[List[int]]
        :type source: int
        :type destination: int
        :rtype: bool
        """
        m = collections.defaultdict(set)
        NOTVISITED, VISITED, VISITING = 0, 1, -1
        states = collections.defaultdict(int)
        # build edges
        for (n1, n2) in edges:
            m[n1].add(n2)

        def dfs(node):
            if states[node] == VISITED:
                # Why?
                return True
            elif states[node] == VISITING:
                return False
            else: # not visited
                if len(m[node]) == 0:
                    return node == destination
                states[node] = VISITING
                for node2 in m[node]:
                    if not dfs(node2): return False
                states[node] = VISITED
                return True

        return dfs(source)

Solution:

// https://code.dennyzhang.com/all-paths-from-source-lead-to-destination
// Basic Ideas: dfs
//
//  Notice:
//  - There would be a circle
//  - Visiting one node twice doesn't gurantee a circle
//
//  No need to examine the same edge twice
//
// Complexity: Time O(n^2), Space O(n)
func dfs(src int, dst int, m []map[int]bool, visited []bool, canreach []bool) {
    if src == dst {
        canreach[src] = true
        return
    }
    // avoid re-examine the same node
    if visited[src] { 
                return 
        }
    visited[src] = true
    for node, _ := range m[src] {
        dfs(node, dst, m, visited, canreach)
        if !canreach[node] {
            canreach[src] = false
            return
        } else {
            canreach[src] = true
        }
    }
}

func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
    visited := make([]bool, n)
    canreach := make([]bool, n)
    m := make([]map[int]bool, n)
    for i, _ := range m { m[i] = map[int]bool{} }
    for _, edge := range edges {
        n1, n2 := edge[0], edge[1]
        m[n1][n2] = true
    }
    if len(m[destination]) != 0 { return false }
    dfs(source, destination, m, visited, canreach)
    return canreach[source]
}

Post Views: 0