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

糖逗

题目描述：

1. 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
   
2. 
   
3. 示例1:
   
4. 
   
5. 输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
   
6. 输出：true
   
7. 示例2:
   
8. 
   
9. 输入：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
   
10. 输出 true
    
11. 提示：
    
12. 
    
13. 节点数量n在[0, 1e5]范围内。
    
14. 节点编号大于等于 0 小于 n。
    
15. 图中可能存在自环和平行边。
    
16. 
    
17. 来源：力扣（LeetCode）
    
18. 链接：https://leetcode-cn.com/problems/route-between-nodes-lcci
    
19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(map<int, vector<int> >&store, bool& res, int start, int target, vector<int>& temp,
   
4.     vector<int>& visit){
   
5.         if(start == target){
   
6.             res = true;
   
7.             return;
   
8.         }
   
9.         if(store.find(start) == store.end()) return;
   
10.         for(int i = 0; i < store[start].size(); i++){
    
11.             if(visit[store[start][i]] == 0){
    
12.                 visit[store[start][i]] = 1;
    
13.                 temp.push_back(store[start][i]);
    
14.                 dfs(store, res, store[start][i], target, temp, visit);
    
15.                 temp.pop_back();
    
16.                 visit[store[start][i]] = 0;
    
17.             }  
    
18.         }
    
19.     }
    
20.     bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
    
21.         //深度优先搜索
    
22.         map<int, vector<int> > store;
    
23.         for(auto cha : graph){
    
24.             store[cha[0]].push_back(cha[1]);
    
25.         }
    
26.         bool res = false;
    
27.         vector<int> temp;
    
28.         vector<int> visit(n, 0);
    
29.         visit[start] = 1;
    
30.         dfs(store, res, start, target, temp, visit);
    
31.         return res;
    
32.     }
    
33. };

复制代码

糖逗