梦始

欧拉回路是这样一个东西（个人理解） ： 从图上某个点出发，每条边不能重复经过，然后从这个点开始把所有的点和边走一遍（同时满足每条边不能重复）后回到这个点。 怎么求？ 一种办法是Fluery , 即每次只找不是桥的边bfs， 当每个点和边都进队后再处理桥， 如果图不连通或者经过桥之后无法遍历整个图，则没有欧拉回路，否则就找到了欧拉回路， 由于这样实现需要先tarjan缩强连通分量后记录桥的位置，之后再每个点遍历，需要时间复杂度大约是O(n ^ 2), 太不牛，我们换下一个算法 Hierholzer算法 （不是这什么鬼名字也太长……）我直接把函数名字写成dfs了，板子如下（自己实现的用起来自己舒服）123456789vector<int> now(n + 1);stack<int> s;auto dfs = [&](auto self, int u) -> void { for (int i = now[u]; i < e[u].size(); i = now[u]) { now[u]++; ...