Leetcode: 1971. Find if Path Exists in Graph

思路

用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