长沙专业网站建设公司排名,运城网站建设专业服务商,做网站也是一门技术,品牌建设的内容文章目录1. 题目2. 解题1. 题目
给定有向图的边 edges#xff0c;以及该图的始点 source 和目标终点 destination#xff0c;确定从始点 source 出发的所有路径是否最终结束于目标终点 destination#xff0c;即#xff1a;
从始点 source 到目标终点 destination 存在至…
文章目录1. 题目2. 解题1. 题目
给定有向图的边 edges以及该图的始点 source 和目标终点 destination确定从始点 source 出发的所有路径是否最终结束于目标终点 destination即
从始点 source 到目标终点 destination 存在至少一条路径如果存在从始点 source 到没有出边的节点的路径则该节点就是路径终点。从始点source到目标终点 destination 可能路径数是有限数字
当从始点 source 出发的所有路径都可以到达目标终点 destination 时返回 true否则返回 false。
示例 1
输入n 3, edges [[0,1],[0,2]], source 0, destination 2
输出false
说明节点 1 和节点 2 都可以到达但也会卡在那里。示例 2
输入n 4, edges [[0,1],[0,3],[1,2],[2,1]], source 0, destination 3
输出false
说明有两种可能在节点 3 处结束或是在节点 1 和节点 2 之间无限循环。示例 3
输入n 4, edges [[0,1],[0,2],[1,3],[2,3]], source 0, destination 3
输出true示例 4
输入n 3, edges [[0,1],[1,1],[1,2]], source 0, destination 2
输出false
说明从始点出发的所有路径都在目标终点结束
但存在无限多的路径如 0-1-20-1-1-20-1-1-1-20-1-1-1-1-2 等。示例 5
输入n 2, edges [[0,1],[1,1]], source 0, destination 1
输出false
说明在目标节点上存在无限的自环。提示
给定的图中可能带有自环和平行边。
图中的节点数 n 介于 1 和 10000 之间。
图中的边数在 0 到 10000 之间。
0 edges.length 10000
edges[i].length 2
0 source n - 1
0 destination n - 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/all-paths-from-source-lead-to-destination 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
题目意思终点只有一个且没有环
class Solution {
public:bool leadsToDestination(int n, vectorvectorint edges, int source, int destination) {vectorbool visited(n, false);vectorvectorint m(n);for(auto e : edges)m[e[0]].push_back(e[1]);if(!m[destination].empty())return false;//终点后面还有路径return dfs(m,visited,source,destination);}bool dfs(vectorvectorint m, vectorbool visited, int cur, int destination) {if(m[cur].size()0 cur ! destination)return false;//到达一个终点但不是目标点for(int next : m[cur])//往下走{if(visited[next])//访问过了return false;//有环visited[next] true;//访问if(!dfs(m, visited, next, destination))return false;visited[next] false;//回溯}return true;}
};128 ms 23.8 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
