题目意思 给定一个有 nnn 个点和 mmm 条边的简单无向图（无重边和自环），若有长度为奇数的环，则输出任意奇环的成员，否则输出 -1 。 错误思路 看到环的那一刻，我想起了拓扑排序，但是这是无向图，且在复杂的图中拓扑排序没有前途。 这张图中拓扑排序在开始就结束了，仅能证明有环，而且在无向图中非常艰难。 正解 这种题是 DFS 奇环检测的模板题。 算法思路 1.在图中随便找一棵树。 2.对树进行二分图染色。 3.寻找是否有连接同色点的边，并根据题目要求解题。在该题中要储存这个环的成员并输出。 思路上可能有的问题 为什么连接同色点的边就会有奇环？ 1.对于有一棵有 numnumnum 个点的树，有 num−1num-1num−1 条边。若再增加一条边则必然产生环。 2.对于一个环，进行二分图染色，两色交替出现，代表已染色的点数奇偶性在改变，与起点颜色相同则是奇数点数，反之则是偶数点数。当两同色点相邻，则相当于起点与终点颜色相同环的成员数为奇数。 如图所示。 绿色代表建树是连接的边，图中进行的是红黑染色，蓝实线是可选择的奇环添加的边，蓝虚线表示理论上可以但题目未给出的边。 存不存在要连接两个或多个边才会出现奇环的情况？ 存在，但不考虑，因为我们只求任意一个奇环，以上情况必然会有一条连接同色点的边，只要有这条边就能找到奇环，不再需要其他边。若没有连接同色点的边，则剩下的边只能组成偶环或者根本没有环。这就是我们只考虑连接一条边的原因。 在代码中如何实现？ 染色和建树可以在同一个 DFS 中完成。 我们可以在建树和染色的同时，判断有没有连接同色点的边。并用栈存放。 如图在 DFS 形成的绿色长链上，到了像蓝色符合条件连接链的边，那么就可以用 vector 倒退存储栈中内容，直到存到图中的节点2停下。 细节见以下代码： 代码中可能有的问题 DFS 时遇到了符合要求且曾经访问过但不在 PA 中的点怎么办？& 为什么能用以上方法求出一个奇环？ 不会遇到，曾经访问过的未找到符合要求边的节点，在后续的 DFS 中没有影响。如图，若代码先将1、2、3、4、5、6进入缓存栈中，5、6在后续出栈，5、6虽然被访问但是是对后续没有任何作用才出栈的。所以用该方法是可行的。 温馨提示 由于没规定所有点都连通，所以可能有多个分离的点集合，所以不能特判 n≤m−1n \le m-1n≤m−1 输出 -1。况且要保证每个点都访问。