使用「深度优先搜索」来判断图中是否存在回路，该题目出自 2018 年阿里巴巴手机淘宝 iOS 客户端架构组应届生面试题目。
Description
有一个包含 N 个顶点，M 条边的有向图，以及提供该图是无向图还是有向图，如果 I == 0 则是有向图，I == 1 则是无向图。
Input
N 表示顶点的个数，M 表示边的个数。I 表示是否为无向图，如果 I == 1 则是无向图，如果 I == 0 则是有向图。（0 < N <= 100, 0 < M <= 4000)。接下来 M 行代表边输入两个正整数 A、B（0 < A, B <= N）。代表有一条从 A 指向 B 的边。
Output
如果该图存在环，则输出字符串 Yes，否则输出 No
Sample Input 1
1 | 4 5 0 |
Sample Output 1
1 | NO |
Sample Input 2
1 | 3 3 1 |
Sample Output 2
1 | Yes |
Sample Input 3
1 | 3 2 1 |
Sample Output 3
1 | No |
这道题目出自 2018 年阿里巴巴手机淘宝 iOS 客户端架构组应届生面试题目。当时的场景是口术思路，并没有要求代码实现。
审题
先看一遍题目说明和要求，首先明确了3个变量：代表一张图中顶点数量的 N、代表边数量的 M 和 代表该图是有向图还是无向图的 I。
其中 I 已被明确告知，当 I == 0 为有向图，I == 1 为无向图。
接下来是输入条件，这里又出现了2个变量，代表边方向起点的 A 和代表边方向终点的 B，也就是说，一条边的方向由 A 指向 B 来决定。
随后又给出了这5个变量的值区间:
0 < N <= 1000 < M <= 40000 < A, B <= NI = 0 || 1
题目要求最后输出图中是否存在环的判断结果，如果该图存在环，则输出字符串 Yes，否则输出 No。
那么这里的「环」究竟代表着什么意思呢？我们不妨先带着问题继续往下看。
分析
题中提供了三个输入样例供我们参考，分别都输入了一大串数字，这串数字又是什么意思呢？
我们先来观察一下三个样例中的数字，你是不是发现了什么规律？
没错，全部都是第一行3个数字，其余行2个数字，结合题目给出的输入要求，其实不难看出，第一行的三个数字，分别对应着 N,M 和 I 的值，而下面行的左右分别对应着 A 和 B 的值。这样再回过头去看这3个输入样例，就豁然开朗了。
这串数字代表的含义搞懂了，但是什么是「环」还没弄清楚，不要着急，你虽然不清楚什么是「环」，但是输入样例里已经有了「环」和「非环」的输出状态 Yes 和 No 的区分，我们只需要按照样例输入的值画出图来，就能直观的用可视化的方式看出其中差异，找到判定为「环」的必要条件，Let’s go!
首先画出第一个输入样例所表示的图：
把图画出来之后，一目了然。这是一张有向图，第一个输入样例的输出结果是 No，表示图中不存在「环」，观察这张图，我们暂时先不做结论，继续画第二个样例的图：
第二个样例画出来的是一张无向图，输出结果是 Yes，表示图中存在「环」，你应该已经看出了什么端倪，同样是不要着急做出结论，我们继续画完第三个样例：
第三个样例还是一张无向图，输出结果是 No，标识图中不存在「环」。对比这三张向图，我们终于可以得出一个初步的结论，所谓的「环」，就是顶点之间连接的边产生了一条回路。
特殊情况
但是，一定要所有顶点都连接成一条完整的回路才算做图中存在「环」吗？我们再来看看下面这几种特殊情况：
- 局部产生回路
由于图内局部顶点之前形成回路，所以图中也存在「环」 - 自环
有向图1 -> 1或 无向图1 - 1这种应该也算「环」，称为自环。 - 有向图和无向图对于「环」定义的区别
对于有向图而言，「环」等于回路， (1) -> (2) 、(2) -> (1) 这个是「环」，但对于无向图来说 (1) - (2) 不是「环」。 - 有向图中的回路
在有向图里，产生「环」的必要条件是有一条完整回路，也就是从哪里来，还能回到哪里去，比如(1) -> (2), (2) -> (3), (3) -> (1) 算存在环，但是 (1) -> (2), (1) -> (3), (3) -> (2) 就不存在环，因为没有形成回路。
明确了「环」产生的条件之后，我们就可以开始着手进行答题了。