Question

判断无向图和有向图是否有环

Answer 1

方法1（数学方法） ： 图的顶点数为n，边数为m，若n>=m+1，则无环;否则有环。
方法2 ：使用并查集进行判断。
方法3 ：DFS。使用visited数组辅助判断是否访问过。

方法1 ：拓扑排序。每次取出入度为0为节点，并删除对应的边，如果最后还有节点则有环。
方法2 ：DFS。使用一个color数组表示节点类型，color[i]=0表示该节点未被访问，color[i]=1表示该节点正在当前访问的路径中或该节点存在于环路中，color[i]=2表示该节点是安全不存在于环中的。
参加leetcode 802： https://leetcode-cn.com/problems/find-eventual-safe-states/