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。