题目描述

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

样例

示例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。
图中可能存在自环和平行边。

(bfs) $O(n)$

从起点开始搜，找到target就返回，否则队列空（已经遍历所有连通的点）还没搜到返回false

C++ 代码

class Solution {
public:
    int h[100010],e[100010],ne[100010],idx;
    bool st[100010],isfind = false;
    void bfs(int start,int target)
    {
        int hh = 0 ,tt = 0;
        int q[100010];
        q[0] = start;
        st[start] = true;
        while(hh<=tt)
        {
            int t = q[hh++];
            for(int i = h[t]; ~i; i = ne[i])
            {
                int j = e[i];
                if(j == target)isfind = true;
                if(!st[j])
                {
                    st[j] = true;
                    q[++tt] = j;
                }
            }
        }
    }
    void add(int a,int b)
    {
        e[idx] = b,ne[idx] = h[a],h[a] = idx++;
    }
    void init(vector<vector<int>> graph,int start, int target)
    {
        memset(h,-1,sizeof h);
        for(int i = 0 ; i < graph.size();i++)
        {
            int a = graph[i][0],b = graph[i][1];
            add(a,b);
        }
        bfs(start,target);
    }
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        init(graph,start,target);
        return isfind;
    }
};