问题:
RT,这个问题是我在思考算导上某练习题后联想到的。(可参考前一篇文章)
做法:
显而易见,我们可以对这个有向图进行拓扑排序,如果拓扑排序不能完成对顶点的排序(出现了后向边),说明该图存在环。
当然为了锻炼思维能力(明明是吃饱了撑的),我进行了另外的思考。
比如强连通分量,我们可以求出这个有向图的强连通分量,如果它的强连通分量数量小于|V|,说明有两个以上的点被并到同一个强连通分量中,而同一个强连通分量中的任意两点可以互相到达,说明该图肯定存在环路。
貌似直接DFS是不行的,如果要用DFS肯定要改一下。