优化CSES邮件投递问题中欧拉路径算法的建议请求

你的任务是给城市居民投递邮件，需要找到一条以邮局为起点和终点，且恰好经过每条街道一次的路线。

这个问题本质是寻找无向图的欧拉回路，我用Hierholzer算法实现了代码，但部分测试用例超时，以下是我的代码片段：

LinkedList<Integer> adj[] = new LinkedList[n];

ArrayDeque<Integer> s = new ArrayDeque<>();
s.push(0);
int curr_v = 0;
int g[][] = new int[n][n];
boolean flag = false;
while (!s.isEmpty()) {

    flag = false;
    while(adj[curr_v].size() > 0) {
        int next_v = adj[curr_v].remove();
        if(g[curr_v][next_v] == 1){
            continue;
        }
        flag = true;
        s.push(curr_v);
        g[curr_v][next_v] = 1;
        g[next_v][curr_v] = 1;
        curr_v = next_v;
    }
    if(!flag){
        circuit.add(curr_v + 1);
        curr_v = s.pop();
    }
}

优化建议 #

你的代码超时核心问题在于二维数组标记边的效率极低，以及邻接表删除操作的时间复杂度太高，以下是针对性优化方案：

1. 移除二维数组g[][]，直接操作邻接表删除边
   二维数组g[n][n]在节点规模较大时（比如题目允许的1e5节点）会占用O(n²)内存，既容易内存溢出，每次检查边是否被访问的操作也会累积大量时间开销。正确做法是直接在邻接表中删除已遍历的边（包括无向图的反向边），从根源避免重复处理。

2. 替换邻接表容器，优化删除操作
   LinkedList.remove()默认移除第一个元素，时间复杂度为O(k)（k为当前节点的边数），边数较多时会大幅拖慢速度。建议改用ArrayDeque作为邻接表的节点容器，它的pollLast()方法是O(1)时间复杂度，能显著提升遍历效率。

3. 简化算法逻辑，减少冗余变量
   去掉flag和curr_v这类冗余变量，直接通过栈的peek()方法获取当前节点，逻辑更简洁，同时减少变量操作的额外开销。

修改后的示例代码 #

// 初始化邻接表，用ArrayDeque替代LinkedList
ArrayDeque<Integer> adj[] = new ArrayDeque[n];
for (int i = 0; i < n; i++) {
    adj[i] = new ArrayDeque<>();
}
// 省略读入边并填充邻接表的代码，注意无向图需双向添加边

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(0);
List<Integer> circuit = new ArrayList<>();

while (!stack.isEmpty()) {
    int curr = stack.peek();
    if (!adj[curr].isEmpty()) {
        int next = adj[curr].pollLast();
        // 删除反向边，避免重复处理
        adj[next].remove(Integer.valueOf(curr));
        stack.push(next);
    } else {
        // 当前节点无未处理边，加入回路
        circuit.add(stack.pop() + 1);
    }
}
// Hierholzer算法从终点开始收集节点，最后反转得到正确路径
Collections.reverse(circuit);

额外注意事项 #

• 如果节点数量极大，用Integer.valueOf(curr)删除反向边仍有O(k)开销，可改用HashSet作为邻接表容器，remove()操作是O(1)，且Hierholzer算法不要求边的处理顺序，完全可行。
• 提前检查图的连通性和所有节点度数是否为偶数（欧拉回路的必要条件），避免无效计算。

内容的提问来源于stack exchange，提问作者Mukesh Ranjan