Q1 Find if Path Exists in Graph - LeetCode 1971
Sat Apr 08 2023 16:05:43 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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;
}
}
content_copyCOPY
https://leetcode.com/problems/find-if-path-exists-in-graph/
Comments