还是当前弧优化,以链式前向星为例。
第一种写法:
for (int i = now[u]; i; i = e[i].nxt) {
now[u] = i;
...
}
第二种:
for (int i = now[u]; i; i = now[u]) {
now[u] = e[i].nxt;
...
}
网络流中前者是对的,后者会跑得很慢,原因未知。
欧拉回路中后者是对的,前者跑得很慢,可以用一个菊花图状物(但不完全是)卡到 n2 以上,因为找欧拉路会走得很深很深,多次走到同一个点,以前者的写法每次都要遍历很多遍访问过的出边。