> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/07-13-2022.md).

# 07/13/2022

This question has a really bad description. Anyway, this question asks if all paths from source lead to destination. First thing we need to check is if the node without outgoing edge is the destination node. Second, we need to make sure there is no cycle so that we can meet the requirment that a finite number of paths from source to destionation. 

1. for detecting the cycles in a directed graph. We can color white to represent the node unvisited, color gray for the node processing and color black for the node processed. To make it simpler, we can just use an int array and numbers 0,1,2 for the above color purposes. 
2. First build the graph adjacency list. 
3. Then we call dfs of the souce node
4. for dfs method, the base case is if the color of node is 1, we just return false. Another base case is if the node is leaf node, we need check if this node == destination node.
5. Then for the neignbours node of this node, we set the color to 1. Then if the recursively dfs on the node is false, we return false. otherwise, we set the node to color 2 and return true.

Time O(V)

Space O(V + E)

```
// Some code
class Solution {
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        int[] colors = new int[n];
        List<Integer>[] g = new List[n];
        buildGraph(g, edges);
        return dfs(g, source, destination, colors);  
    }
    
    private void buildGraph(List<Integer>[] g, int[][] edges) {
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] edge: edges) {
            int from = edge[0];
            int to = edge[1];
            g[from].add(to);
        }
        
    }
    
    private boolean dfs(List<Integer>[] g, int s, int d, int[] colors) {
        //base case
        if (colors[s] == 1) return false;
        if (g[s].size() == 0) {
            return s == d;
        }
        colors[s] = 1;
        for (int next: g[s]) {
           if (!dfs(g, next, d, colors)) 
               return false;
        }
        
        colors[s] = 2;
        return true;
    }
}
```