class Solution { public boolean validPath(int n, int[][] edges, int source, int destination) { //make HM for vertices and edges HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>(); for(int edge[] : edges){ int a = edge[0] , b = edge[1]; graph.computeIfAbsent(a , k -> new ArrayList<>()).add(b); graph.computeIfAbsent(b , k -> new ArrayList<>()).add(a); } //to prevent infinite loop between neighours boolean[] visited = new boolean[n]; return dfs(graph , source , destination , visited); } //recursive DFS public boolean dfs(HashMap<Integer,ArrayList<Integer>> graph,int source , int destination , boolean visited[]){ if(source == destination) return true; //mark the source first visited[source] = true; for(int edge : graph.get(source)){ if(visited[edge] == false){ if(dfs(graph , edge , destination , visited)) return true; } } return false; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter