用dps從start點走一遍,然後檢查end點有沒有finish。
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int start, int end) {
vector<vector<int>> adjlist(n);
for(auto el: edges) {
adjlist[el[1]].push_back(el[0]);
adjlist[el[0]].push_back(el[1]);
}
vector<bool> discover(n, false), finish(n, false);
int e = dps(adjlist, discover, finish, start);
if (finish[end])
return true;
else
return false;
}
private:
int dps(vector<vector<int>>& adjlist, vector<bool>& discover, vector<bool>&finish, int curr_node) {
if (discover[curr_node])
return 0;
if (finish[curr_node])
return 0;
discover[curr_node] = true;
for(auto el: adjlist[curr_node])
int e = dps(adjlist, discover, finish, el);
discover[curr_node] = false; finish[curr_node] = true;
return 0;
}
};
遇到
AddressSanitizer:DEADLYSIGNAL
=================================================================
==31==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc4183cfe0 (pc 0x0000003461c1 bp 0x7ffc4183d090 sp 0x7ffc4183cfc0 T0)
==31==ABORTING
這個是遞迴太深造成的,遞迴終止條件沒寫好的關係
參考:
https://ithelp.ithome.com.tw/articles/10268205
https://leetcode.com/problems/find-if-path-exists-in-graph/
https://web.ntnu.edu.tw/~algo/Graph.html#7