1059. All Paths from Source Lead to Destination

 一刷 07/2022

Version #1 DFS

If we want to detect cycle in a graph, we need to keep track of each path with backtracking instead of keep track of the globally visited nodes

Time O(V + E) - for full graph dfs

Space O(V + E) - E is occupied by the adjacency list and V is used by the system stack

Runtime: 6 ms, faster than 94.73% of Java online submissions for All Paths from Source Lead to Destination.

Memory Usage: 45.3 MB, less than 93.00% of Java online submissions for All Paths from Source Lead to Destination.

class Solution {

    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {

        // If there's any cycles, then return false

        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            graph.add(new ArrayList<>());

        }

        for (int[] edge : edges) {

            // edge[0] -> edge[1]

            graph.get(edge[0]).add(edge[1]);

        }

        Set<Integer> path = new HashSet<>();

        path.add(source);

        return dfs(graph, source, destination, path);

    }

    

    private boolean dfs(List<List<Integer>> graph, int node, int destination, Set<Integer> path) {

        if (graph.get(node).size() == 0) {

            return node == destination;

        }

        for (Integer next : graph.get(node)) {

            if (!path.add(next)) {

                return false;

            }

            path.add(next);

            if (!dfs(graph, next, destination, path)) {

                return false;

            }

            path.remove(next);

        }

        return true;

    }

}