关于欧拉路径的问题

Kniqht @ 2023-10-22 06:56:48

如此优化（在这题中是错的）：
for(int i=now[u];i<=n;i=now[u]){
        now[u]=i+1;
        if(g[u][i]>0){
            g[u][i]--;g[i][u]--;
            dfs(i);
        }
    }

by Comentropy @ 2023-10-26 16:37:22

当前弧优化是针对边的，网路流中也有类似优化。

by Michael_Liu @ 2023-11-03 14:55:03

@Kniqht 是可以当前弧优化的啊,我是加了的

#include <bits/stdc++.h>
#define ll long long
#define reg register
using namespace std;
const int N=510;
vector<int> edge[N];
stack<int> st;
int cur[N];
int cnt[N][N];
inline void dfs(int p){
    int sz=edge[p].size();
    for(reg int i=cur[p];i<sz;i=cur[p]){
        cur[p]=i+1;
        int to=edge[p][i];
        if(cnt[p][to]==0) continue;
        cnt[p][to]--;cnt[to][p]--;
        dfs(to);
    }
    st.push(p);
}
int du[N],s,t;
int num=0;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n=0,m;
    cin>>m;
    for(reg int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);edge[v].push_back(u);
        cnt[u][v]++;cnt[v][u]++;
        du[u]++;du[v]++;
        n=max(n,max(u,v));
    }
    for(reg int i=1;i<=n;++i){
        sort(edge[i].begin(),edge[i].end());
        if(du[i]&1) if(!s) s=i;
    }
    if(!s) s=1;
    dfs(s);
    while(!st.empty()) {cout<<st.top()<<'\n';st.pop();}
    return 0;
}