解法一：DFS

1、思路

• 将每条有向边添加到图中，用一个vector<unordered_set>结构来表示图，它的键代表一个节点，值代表这个节点所能到达的所有节点集；

• 再用一个isVisited布尔数组来记录每个节点是否访问过；

• 时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

2、代码

class Solution {
public:
    void dfs(vector<unordered_set<int>>& hash, vector<bool>& isVisited, int start, int target,
                bool& flag)
    {
        if (start == target)
        {
            flag = true;
        }

        isVisited[start] = true;        //标记已经来过
        for (int next : hash[start])
        {
            if (!isVisited[next])       //若未访问过，则继续 dfs
            {
                dfs(hash, isVisited, next, target, flag);
            }
        }
        isVisited[start] = false;       //还原现场
    }

    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        vector<unordered_set<int>> hash(n);
        vector<bool> isVisited(n, false);
        bool flag = false;

        for (vector<int>& path : graph)
        {
            hash[path[0]].insert(path[1]);  //构造图
        }

        dfs(hash, isVisited, start, target, flag);

        return flag;
    }
};

解法二：BFS

1、思路

同上。

2、代码

class Solution {
public:
    bool bfs(vector<unordered_set<int>>& hash, vector<bool>& isVisited, int start, int target)
    {
        queue<int> q;
        q.push(start);
        isVisited[start] = true;

        while (!q.empty())
        {
            int cur = q.front();
            q.pop();

            for (int next : hash[cur])
            {
                if (!isVisited[next])
                {
                    if (next == target) return true;
                    q.push(next);
                    isVisited[next] = true;
                }
            }
        }

        return false;
    }

    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        vector<unordered_set<int>> hash(n);
        vector<bool> isVisited(n, false);

        for (vector<int>& path : graph)
        {
            hash[path[0]].insert(path[1]);
        }

        return bfs(hash, isVisited, start, target);
    }
};