C++刷leetcode（面试题 04.01. 节点间通路）【深度优先搜索】【图】

糖逗

题目描述：

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例1:

 输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 输出：true
示例2:

 输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 输出 true
提示：

节点数量n在[0, 1e5]范围内。
节点编号大于等于 0 小于 n。
图中可能存在自环和平行边。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/route-between-nodes-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    void dfs(map<int, vector<int> >&store, bool& res, int start, int target, vector<int>& temp,
    vector<int>& visit){
        if(start == target){
            res = true;
            return;
        } 
        if(store.find(start) == store.end()) return;
        for(int i = 0; i < store[start].size(); i++){
            if(visit[store[start][i]] == 0){
                visit[store[start][i]] = 1;
                temp.push_back(store[start][i]);
                dfs(store, res, store[start][i], target, temp, visit);
                temp.pop_back();
                visit[store[start][i]] = 0;
            }  
        }
    }
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        //深度优先搜索
        map<int, vector<int> > store;
        for(auto cha : graph){
            store[cha[0]].push_back(cha[1]);
        }
        bool res = false;
        vector<int> temp;
        vector<int> visit(n, 0);
        visit[start] = 1;
        dfs(store, res, start, target, temp, visit);
        return res;
    }
};

糖逗