令G =（v，e）有向图。令V为G中的顶点，找到参与非简单的定向路径的顶点的数量
令G =（v，e）有向图。
让V为G中的顶点，找到参与非简单的定向路径的顶点的数量到
我的尝试：
查找牢固连接的组件，v_1，v_1，v_2 ...，v_i（使用DFS搜索产生） 。
在v_1，v_2 ...，v_i。
上执行拓扑排序假设v in v_j中的v。 在V_1上执行DFS到V_J，并在紧密连接中计数所有顶点 大小大于1的组件。
我的解决方案正确吗？
Let G=(V, E) directed graph.
Let v be a vertex in G, find the number of vertices that take part in non-simple directed paths to v.
My attempt:
Find strongly connected components , V_1,V_2...,V_i (using DFS search produces).
Perform topological sorting on the V_1,V_2...,V_i.
Suppose v in V_j.
Perform DFS on V_1 to V_j and count all vertex in the strongly connected
components whose size is bigger than 1.
Is my solution correct?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
第一步：检查您的图表是否周期。它没有，然后没有非简单路径。
第二：检查您的图表是否计数。如果有1个组件，则参与非简单有向路径的顶点数量等于图中的顶点数量，因为每个顶点都可以在一个周期中转到一个顶点，绕周期绕过一个周期，并继续继续目的地。
第三：检查包含v的循环的组件。它没有，那么没有非简单路径。否则，参与非简单有向路径的顶点数量等于组件中的顶点数量。
First step: check your graph for cycles. It there are none, then there are no non-simple paths..
Second: check your graph for component count. If there is 1 component then the number of vertices that take part in non-simple directed paths is equal to the number of vertices in the graph, because every vertex can go to a vertex in a cycle, go around the cycle, and continue to the destination.
Third: Check the component that contains v for cycles. It there are none, then there are no non-simple paths. Otherwise the number of vertices that take part in non-simple directed paths is equal to the number of vertices in the component.