Find a available path from a given source to a given destination in a given graph.
Intuition
Use DFS to find all reachable nodes and check if the destination lie within those nodes.
Approach
We first transform the adjacency matrix to adjacency list to make BFS easier, then we use
a queue to maintain the reachable nodes, to prevent from cycling, we also use a set to keep track of visited nodes.
If at any point, we reach the destination, we return directly.
Complexity
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
unordered_map<int, vector<int>> adjs;
for (const auto &edge: edges) {
adjs[edge[0]].push_back(edge[1]);
adjs[edge[1]].push_back(edge[0]);
}
unordered_set<int> visited;
queue<int> q;
q.push(source);
while (!q.empty()) {
int node = q.front();
q.pop();
if (node == destination) return true;
for (int next_node: adjs[node]) {
if (visited.find(next_node) != visited.end())
continue;
q.push(next_node);
visited.insert(next_node);
}
}
return false;
}
};
|