> 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/06-28-2022-1971.md).

# 06/28/2022 1971

//recursion stack

```
// Some code
class Solution {
    public boolean validPath(int n, int[][] edges, int start, int end) {
        List<Integer>[] adj = new ArrayList[n];
        
        for(int i=0; i<n; i++)
            adj[i] = new ArrayList<>();
        
        for(int[] edge: edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        
        boolean[] visited = new boolean[n];
        
        if(dfs(visited, adj, start, end))
            return true;
        
        return false;
    }
    
    public boolean dfs(boolean[] visited, List<Integer>[] adj, int start, int end) {
        if(start == end)
            return true;
        visited[start] = true;
        
        for(int i: adj[start]) {
            if(visited[i] == true)
                continue;
            if(dfs(visited, adj, i, end))
                return true;
        }
        return false;
    }
}
```

```
// Some code
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        boolean visited[] = new boolean[n];
        
        for(int i=0;i<n;i++){
            adj.add(new ArrayList<>());
        }
        for(int edge[]:edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
       
        dfs(source,destination,visited,adj);    
        return visited[destination];
    }
    
    private void dfs(int start,int dest,boolean visited[], ArrayList<ArrayList<Integer>> adj){
        
        visited[start]=true;
        if(start==dest){
            return ;
        }
        
        for(int adjacent : adj.get(start)){
            if(!visited[adjacent]){
                dfs(adjacent,dest,visited,adj);
            }
        }        
    }
}
```

```
// Some code
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        boolean visited[] = new boolean[n];
        
        for(int i=0;i<n;i++){
            adj.add(new ArrayList<>());
        }
        for(int edge[]:edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
                
        queue.add(source);
        visited[source]=true;
		
        while(!queue.isEmpty()){
            int curr = queue.remove();
            visited[curr]=true;
            for(int adjacent : adj.get(curr)){
                if(!visited[adjacent]){
                    if(adjacent==destination){
                        return true;
                    }
                    queue.add(adjacent);
                    visited[adjacent]=true;
                }
            }
        }        
        return visited[destination];
    }
}
```

//explicit stack

```
// Some code
class Solution {
    public boolean validPath(int n, int[][] edges, int start, int end) {
    
    //first build the graph with the adjacency_list
        List<List<Integer>> adjacency_list = new ArrayList<>();        
        for (int i = 0; i < n; i++) {
            adjacency_list.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            adjacency_list.get(edge[0]).add(edge[1]);
            adjacency_list.get(edge[1]).add(edge[0]);
        }
        
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        boolean seen[] = new boolean[n];
        Arrays.fill(seen, false);
        
        while (!stack.isEmpty()) {
            // Get the current node.
            int node = stack.pop();
            
            // Check if we have reached the target node.
            if (node == end) {
                return true;
            }
            
            // Check if we've already visited this node.
            if (seen[node]) {
                continue;
            }
            seen[node] = true;
            
            // Add all neighbors to the stack.
            for (int neighbor : adjacency_list.get(node)) {
                stack.push(neighbor);
            }
        }
        
        return false;
    }
}
```