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


  • Approach:

    1. Built the graph with given edges.

    2. Run a DFS from the source.

    3. Check if the destination is reached or not.

    4. 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);

}

};