Skip to main content

Depth First Search

All Paths from Source Lead to Destination - LeetCode Premium

Problem Statement

Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, 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.

We will use Color enum which represents the state of each node as follows:

WHITE ~ Vertex has not been processed yet. Initially, all vertices are WHITE.
GRAY ~ Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (in the DFS tree) of this vertex are not processed yet (or this vertex is in the function call stack).
BLACK ~ Vertex and all its descendants are processed.

Video Explanation

Java Code

enum Color {
    WHITE,
    GRAY,
    BLACK
}

class Solution {

    public List<List<Integer>> buildGraph(int[][] edges, int n) {
        List<List<Integer>> graph = new ArrayList<>();
        
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }

        return graph;
    }

    boolean dfs(int node, int dest, List<List<Integer>> graph, Color[] state) {
        if (state[node] != Color.WHITE) {
            return state[node] == Color.BLACK;
        }
        
        if (graph.get(node).isEmpty()) {
            return node == dest;
        }

        state[node] = Color.GRAY;

        for(int nbr: graph.get(node)) {
            if(!dfs(nbr, dest, graph, state)) {
                return false;
            }    
        }
        
        state[node] = Color.BLACK;
        return true;
    }

    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> graph = buildGraph(edges, n);
        Color[] state = new Color[n];
        Arrays.fill(state, Color.WHITE);
        return dfs(source, destination, graph, state);
    }
}

C++ Code

enum Color {
    WHITE,
    GRAY,
    BLACK
};

class Solution {
public:
    vector<vector<int>> buildGraph(vector<vector<int>>& edges, int n) {
        vector<vector<int>> graph(n);

        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
        }

        return graph;
    }

    bool dfs(int node, int dest, vector<vector<int>>& graph, vector<Color>& state) {
        if (state[node] != Color::WHITE) {
            return state[node] == Color::BLACK;
        }

        if (graph[node].empty()) {
            return node == dest;
        }

        state[node] = Color::GRAY;

        for (int nbr : graph[node]) {
            if (!dfs(nbr, dest, graph, state)) {
                return false;
            }
        }

        state[node] = Color::BLACK;
        return true;
    }

    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph = buildGraph(edges, n);
        vector<Color> state(n, Color::WHITE);
        return dfs(source, destination, graph, state);
    }
};

Python Code

from enum import Enum

class Color(Enum):
    WHITE = 0
    GRAY = 1
    BLACK = 2

class Solution:

    def buildGraph(self, edges, n):
        graph = [[] for _ in range(n)]

        for edge in edges:
            graph[edge[0]].append(edge[1])

        return graph

    def dfs(self, node, dest, graph, state):
        if state[node] != Color.WHITE:
            return state[node] == Color.BLACK

        if not graph[node]:
            return node == dest

        state[node] = Color.GRAY

        for nbr in graph[node]:
            if not self.dfs(nbr, dest, graph, state):
                return False

        state[node] = Color.BLACK
        return True

    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = self.buildGraph(edges, n)
        state = [Color.WHITE] * n
        return self.dfs(source, destination, graph, state)

Complexity Analysis

Time Complexity: For an entire DFS over an input graph, it takes O(V + E), where V represents the number of vertices in the graph and E represents the number of edges in the graph.

Space Complexity: O(V + E) where O(E) is occupied by the adjacency list and O(V) is occupied by the recursion stack and the color states.

Follow us on LinkedIn and connect with us on Discord in case you are stuck or have any questions.