1971. Find if Path Exists in Graph
View on LeetCode ↗
C++
class Solution {public: void dfs(std::vector<std::vector<int>>& adj_list, std::vector<bool>& visited, int source, int& destination, bool& trip) { if (destination == source) trip = true; if (trip == true) return; if (visited[source]) return; visited[source] = true; for (auto& j : adj_list[source]) { dfs(adj_list, visited, j, destination, trip); } } bool validPath(int n, vector<vector<int>>& edges, int source, int destination) { std::vector<std::vector<int>> adj_list(n); std::vector<bool> visited(n, false); for (auto& edge : edges) { adj_list[edge[0]].push_back(edge[1]); adj_list[edge[1]].push_back( edge[0]); // forgot to do bi directional build. } bool trip = false; dfs(adj_list, visited, source, destination, trip); return trip; }};
starting graphs now, just check if path is valid simple. just make adj list and visited for dfs/bfs if i did bfs. needed to make sure i was doing bidirectional setup