C++刷leetcode（面试题 04.01. 节点间通路）【深度优先搜索】【图】
本帖最后由 糖逗 于 2020-6-2 10:52 编辑题目描述：
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例1:
输入：n = 3, graph = [, , , ], start = 0, target = 2
输出：true
示例2:
输入：n = 5, graph = [, , , , , , , , , ], start = 0, target = 4
输出 true
提示：
节点数量n在范围内。
节点编号大于等于 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.size(); i++){
if(visit] == 0){
visit] = 1;
temp.push_back(store);
dfs(store, res, store, target, temp, visit);
temp.pop_back();
visit] = 0;
}
}
}
bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
//深度优先搜索
map<int, vector<int> > store;
for(auto cha : graph){
store].push_back(cha);
}
bool res = false;
vector<int> temp;
vector<int> visit(n, 0);
visit = 1;
dfs(store, res, start, target, temp, visit);
return res;
}
}; {:10_327:}
页:
[1]