我曾经用过几次的,以下求无向图欧拉路径的代码是假的。
void dfs(int u){
for(int i=h[u],v=to[i];i;v=to[i=nxt[i]]){
h[u]=nxt[i];
if(!vis[i]&&!vis[i^1])
vis[i]=vis[i^1]=1,dfs(v);
}
ans[t++]=u;
}
至少常数会极大,因为存在可能是在未来标记过的边在回溯后仍被遍历,虽然因为那个 if 不会再走但还是会遍历到,然后就很难受了。
我之前写的经常是有向图的,不需要判反向边,所以一般写成 vector,我 vector 的写法是真的,然后加上一些题数据水了之前没注意到,导致了今天用这个写法的时候爆了几个点。
应该这样写。
void dfs(int u){
for(int i=h[u],v=to[i];i;v=to[i=nxt[i]]){
h[u]=nxt[i];
if(!vis[i]&&!vis[i^1])
vis[i]=vis[i^1]=1,dfs(v),nxt[i]=h[u];
}
ans[t++]=u;
}