关于dfs中用dis判断而非用vis判断的疑问
查看原帖
关于dfs中用dis判断而非用vis判断的疑问
674793
luoguhandongheng楼主2025/8/5 12:05
void dfs(int u, int d){
    if(dis[u]){ // 这一行
        ans = __gcd(ans, abs(dis[u] - d));
        return ;
    }
    dis[u] = d, vis[u] = 1;
    chmax(maxx, dis[u]), chmin(minx, dis[u]);
    for(auto [v, w] : e[u])
        dfs(v, d + w);
}

这里是用 dis 来判断是否访问过的。但实际上这是有问题的,因为由于原图有负边,所以 dis 为 0 的点不一定被访问过。

比如这个图 如果按照一种特定的访问顺序,比如 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 此时 dis[7] = dis[1] = 0,那么 7 如果再访问 1 的话 dis[1] 就变成了 -1,然后就错了。

但是按照正常的 vector 建图。

for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        e[v].emplace_back(u, -1);
        e[u].emplace_back(v, 1);
    }

好像程序不会按照这种特定的访问顺序。

所以想请问,这里写 vis[u] 和 dis[u] 是等价的吗,还是会有hack。

2025/8/5 12:05
加载中...