已知有向图具有n个顶点 判断图中是否存在有向回路

Question

需要盖要描述算法的思想，并且在关键的地方给出简明的注释，使用c语言。

Answer 1

正确的解法应该有两种：
1.拓扑
2.dfs（深搜）
回路的定义这里就不必再说了（毕竟我蒟QwQ）
第一种方法是利用了拓扑排序的思想，在拓扑排序的过程中，我们往往需要保证图中没有回路，所以可以利用这个算法的边界：
我们就正常进行拓扑序遍历：1.找到入度为零的点输出；2.删除与这些点相关的出度；3.重复上述直到图中不存在入度为零的点为止
结束的时候判断一下，如果所有点都被输出了一遍，说明是没有回路的（就和我们平时走拓扑序一样，既然能成功，图就是没有回路的），反之则反（当然如果找不到入度为零的点就直接操作三）
第二种方法相对简单一些，我们循环所有节点作为源点，从源点开始遍历，就写一个深搜的板子，再加一个判断：如果深搜的过程中遇到了源点就说明有回路（注意，这里和楼上的区别在于：我判断的是从某个点出发能否回到这个节点，而楼上判断的是某个节点被碰到过一次后是否会被再碰到一次，可以画几个图加深理解）
（但是很显然搜索这个东西不剪纸和记忆化效率是比较……嗯……可能还比较玄学，所以个人喜欢用拓扑）

Answer 2

我是c++党，个人听闻c和c++好像差不多来着，这上面也没涉及STL，应该可以描述一下：
深搜就不说了
拓扑的话，用in来保存一个点的入度就可以了，删点操作的话可以使用“假删点”，就是从这个节点出发，对于所有连边指向的节点v，进行操作in[v]--；然后其实就没东西了……

Answer 3

楼下的评论回复给了我一点启发，好像可以用有向图的强连通分量去判定是否存在有向回路，先进行一边dfs记录每个点的时间戳dfn，然后再套模版更新low是不是也可以，这样好像还更通用【关于我总是喜欢用超级源点导致调爆这件事】
tarjan模版：https://www.bilibili.com/video/BV19J411J7AZ?spm_id_from=333.337.search-card.all.click （没错备赛刚看过😅）