C++ 深度优先搜索 (DFS) 回溯优化：在循环前后重置 vis 数组

在深度优先搜索 (DFS) 中，回溯时重置 vis 数组，可以在 for 循环后面赋值为 0，也可以在 for 循环里面赋值为 0。两种方式是等价的，因为在 for 循环结束后，vis 数组的状态已经被恢复了。

例如，以下代码展示了两种方式：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int g[N][N], dist, max_d = -10 * N, n, m;
boolean vis[N];

void dfs(int st) {
    for (int i = 1; i <= n; i++) {
        if (g[st][i] && !vis[i]) {
            vis[i] = 1;
            dist += g[st][i];
            dfs(i);
            dist -= g[st][i]; // 回溯
            vis[i] = 0; // 在循环内重置
        }
    }
    max_d = max(max_d, dist); // 统计最大深度
    vis[st] = 0; // 在循环后重置
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z; // 读入边和对应的权值
        g[x][y] = z;
        g[y][x] = z;
    }
    for (int i = 1; i <= n; i++) {
        vis[i] = 1;
        dfs(i);
        memset(vis, 0, sizeof(vis)); // 记得清空标记数组
    }
    cout << max_d;
    return 0;
}

两种方式都能够正确地进行回溯，但在代码可读性和规范性上，建议在 for 循环后面统一回溯。

建议：

为了代码的可读性和规范性，建议在 for 循环后面统一进行回溯操作，例如：

void dfs(int st) {
    for (int i = 1; i <= n; i++) {
        if (g[st][i] && !vis[i]) {
            vis[i] = 1;
            dist += g[st][i];
            dfs(i);
            dist -= g[st][i]; // 回溯
        }
    }
    vis[st] = 0; // 在循环后重置
    max_d = max(max_d, dist); // 统计最大深度
    return;
}

这样可以使代码更易于理解和维护。

总结：

在 for 循环前后重置 vis 数组都是有效的回溯方法，但建议在 for 循环后面统一进行回溯操作，以提高代码可读性和规范性。