Description

有一个包含 N 个顶点,M 条边的有向图,以及提供该图是无向图还是有向图,如果 I == 0 则是有向图,I == 1 则是无向图。

Input

N 表示顶点的个数,M 表示边的个数。I 表示是否为无向图,如果 I == 1 则是无向图,如果 I == 0 则是有向图。(0 < N <= 100, 0 < M <= 4000)。接下来 M 行代表边输入两个正整数 AB0 < A, B <= N)。代表有一条从 A 指向 B 的边。

Output

如果该图存在环,则输出字符串 Yes,否则输出 No

Sample Input 1

4 5 0
1 2
2 3
1 3
1 4
2 4

Sample Output 1

NO

Sample Input 2

3 3 1
1 2
1 3
2 3

Sample Output 2

Yes

Sample Input 3

3 2 1
1 2
2 3

Sample Output 3

No

这道题目出自 2018 年阿里巴巴手机淘宝 iOS 客户端架构组应届生面试题目。当时的场景是口术思路,并没有要求代码实现。

审题

先看一遍题目说明和要求,首先明确了3个变量:代表一张图中顶点数量的 N、代表边数量的 M 和 代表该图是有向图还是无向图的 I

其中 I 已被明确告知,当 I == 0 为有向图,I == 1 为无向图。

接下来是输入条件,这里又出现了2个变量,代表边方向起点的 A 和代表边方向终点的 B,也就是说,一条边的方向由 A 指向 B 来决定。

随后又给出了这5个变量的值区间:

  • 0 < N <= 100
  • 0 < M <= 4000
  • 0 < A, B <= N
  • I = 0 || 1

题目要求最后输出图中是否存在环的判断结果,如果该图存在环,则输出字符串 Yes,否则输出 No

那么这里的「环」究竟代表着什么意思呢?我们不妨先带着问题继续往下看。

分析

题中提供了三个输入样例供我们参考,分别都输入了一大串数字,这串数字又是什么意思呢?

我们先来观察一下三个样例中的数字,你是不是发现了什么规律?

没错,全部都是第一行3个数字,其余行2个数字,结合题目给出的输入要求,其实不难看出,第一行的三个数字,分别对应着 N,MI 的值,而下面行的左右分别对应着 AB 的值。这样再回过头去看这3个输入样例,就豁然开朗了。

这串数字代表的含义搞懂了,但是什么是「环」还没弄清楚,不要着急,你虽然不清楚什么是「环」,但是输入样例里已经有了「环」和「非环」的输出状态 YesNo 的区分,我们只需要按照样例输入的值画出图来,就能直观的用可视化的方式看出其中差异,找到判定为「环」的必要条件,Let's go!

首先画出第一个输入样例所表示的图:
有向图

把图画出来之后,一目了然。这是一张有向图,第一个输入样例的输出结果是 No,表示图中不存在「环」,观察这张图,我们暂时先不做结论,继续画第二个样例的图:
无向图1

第二个样例画出来的是一张无向图,输出结果是 Yes,表示图中存在「环」,你应该已经看出了什么端倪,同样是不要着急做出结论,我们继续画完第三个样例:
无向图2

第三个样例还是一张无向图,输出结果是 No,标识图中不存在「环」。对比这三张向图,我们终于可以得出一个初步的结论,所谓的「环」,就是顶点之间连接的边产生了一条回路

特殊情况

但是,一定要所有顶点都连接成一条完整的回路才算做图中存在「环」吗?我们再来看看下面这几种特殊情况:

  1. 局部产生回路
    特殊情况1-局部环
    由于图内局部顶点之前形成回路,所以图中也存在「环」
  2. 自环
    特殊情况2-自环
    有向图 1 -> 1 或 无向图 1 - 1 这种应该也算「环」,称为自环。
  3. 有向图和无向图对于「环」定义的区别
    特殊情况3-有向无向区别
    对于有向图而言,「环」等于回路, (1) -> (2) 、(2) -> (1) 这个是「环」,但对于无向图来说 (1) - (2) 不是「环」。
  4. 有向图中的回路
    特殊情况4-有向图回路
    有向图里,产生「环」的必要条件是有一条完整回路,也就是从哪里来,还能回到哪里去,比如(1) -> (2), (2) -> (3), (3) -> (1) 算存在环,但是 (1) -> (2), (1) -> (3), (3) -> (2) 就不存在环,因为没有形成回路

明确了「环」产生的条件之后,我们就可以开始着手进行答题了。