图论为什么用ACM模式.md

图论为什么统一使用ACM模式

代码随想录图论章节给大家统一换成ACM输入输出模式。

图论是在笔试还有面试中，通常都是以ACM模式来考察大家，而大家习惯在力扣刷题（核心代码模式），核心代码模式对图的存储和输出都隐藏了。

而图论题目的输出输出 相对其他类型题目来说是最难处理的。

ACM模式是最考察候选人对代码细节把控程度的， 图的构成，图的输出，这些只有ACM输入输出模式才能体现出来。

输入的细节

图论的输入难在 图的存储结构，如果没有练习过 邻接表和邻接矩阵 ，很多录友是写不出来的。

而力扣上是直接给好现成的 数据结构，可以直接用，所以练习不到图的输入，也练习不到邻接表和邻接矩阵。

如果连邻接表 和 邻接矩阵都不知道或者写不出来的话，可以说 图论没有入门。

举个例子，对于力扣 797.所有可能的路径 ，录友了解深度优先搜索之后，这道题目就是模板题，是送分题。

如果面试的时候出一道原题 （笔试都是ACM模式，部分面试也是ACM模式），不少熟练刷力扣的录友都难住了，因为不知道图应该怎么存，也不知道自己存的图如何去遍历。

即使面试的时候，有的面试官，让你用核心代码模式做题，当你写出代码后，面试官补充一句：这个图 你是怎么存的？

难道和面试官说：我只知道图的算法，但我不知道图怎么存。

后面大家在刷 代码随想录图论第一题98. 所有可达路径 的时候，就可以感受到图存储的难点所在。

所以这也是为什么我要让大家练习 ACM模式，也是我为什么 在代码随想录图论讲解中，不惜自己亲自出题，让大家统一练习ACM模式。

输出的细节

同样，图论的输出也有细节，例如 求节点1 到节点5的所有路径， 输出可能是：

1 2 4 5
1 3 5

表示有两条路可以到节点5， 那储存这个结果需要二维数组，最后在一起输出，力扣是直接return数组就好了，但 ACM模式要求我们自己输出，这里有就细节了。

就拿 只输出一行数据，输出 1 2 4 5 来说，

很多录友代码可能直接就这么写了：

for (int i = 0 ; i < result.size(); i++) {
    cout << result[i] << " ";
}

这么写输出的结果是 1 2 4 5 ， 发现结果是对的，一提交，发现OJ返回 格式错误 或者 结果错误。

如果没练习过这种输出方式的录友，就开始怀疑了，这结果一样一样的，怎么就不对，我在力扣上提交都是对的！

大家要注意，5 后面要不要有空格！

上面这段代码输出，5后面是加上了空格了，如果判题机判断 结果的长度，标准答案1 2 4 5长度是7，而上面代码输出的长度是 8，很明显就是不对的。

所以正确的写法应该是：

for (int i = 0 ; i < result.size() - 1; i++) {
    cout << result[i] << " ";
}
cout << result[result.size() - 1];

这么写，最后一个元素后面就没有空格了。

这是很多录友经常疏忽的，也是大家刷习惯了 力扣（核心代码模式）根本不会注意到的细节。

同样在工程开发中，这些细节都是影响系统稳定运行的因素之一。

ACM模式 除了考验算法思路，也考验 大家对 代码的把控力度， 而 核心代码模式 只注重算法的解题思路，所以输入输出这些就省略掉了。

其他

大家如果熟练ACM模式，那么核心代码模式没问题，但反过来就不一定了。

而且我在讲解图论的时候，最头疼的就是找题，在力扣上 找题总是找不到符合思路且来完整表达算法精髓的题目。

特别是最短路算法相关的题目，例如 Bellman_ford系列 ，Floyd ，A * 等等总是找不到符合思路的题目。

索性统一我自己来出题，这其中也是巨大的工作量。为了给大家带来极致的学习体验，我在很多细节上都下了功夫。

等大家将图论刷完，就会感受到我的良苦用心。加油