Leetcode刷题笔记题解（C++）：1971. 寻找图中是否存在路径

思路：

1.建立图集，二维数组，path[0]里面存放的就是与0相连的节点集合

2.用布尔数组来记录当前节点是否被访问过，深度优先会使用到

3.遍历从起点开始能直接到达的点（即与起点相邻的点），判断那个点是否已经走过，并进入递归继续遍历与那个点相邻的点，直到抵达终点。

class Solution {
public:
    bool visted[200000];//记录当前节点是否访问过
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>>path(n);//保存图集，节点---节点相连的节点集合
        for(int i = 0;i <edges.size();i++){
            path[edges[i][0]].push_back(edges[i][1]);//建立图集
            path[edges[i][1]].push_back(edges[i][0]);
        }
        return dfs(path,source,destination);
    }
    bool dfs(vector<vector<int>>& path, int source, int destination){
        visted[source] = true;//记录当前节点已经被访问过了
        if(source == destination) return true;//如果source为目标节点了则返回真
        for(int i = 0;i < path[source].size();i++){
            //如果下一节点没有被访问过且深度优先搜索为真则返回真
            if(visted[path[source][i]] == false && dfs(path,path[source][i],destination)) return true;
        }
        return false;
    }
};