hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Find if Path Exists in Graph
Problem: 1971. Find if Path Exists in Graph
Problem Link: leetcode.com/problems/find-if-path-exists-in-graph/
Approach:
Built the graph with given edges.
Run a DFS from the source.
Check if the destination is reached or not.
If reached returned true else returned false.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N)
Code [C++]
class Solution {
public:
vector<int>graph[200005];
bool visited[200005];
bool dfs(int src, int dest){
visited[src] = true;
if(src == dest) return true;
bool ret = false;
for(int i=0; i<size(graph[src]); i++){
int v = graph[src][i];
if(!visited[v]){
ret = ret | dfs(v, dest);
}
}
return ret;
}
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
for(int i=0; i<size(edges); i++){
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
memset(visited, false, sizeof(visited));
return dfs(source, destination);
}
};