复习心得 - 欧拉路

· · 算法·理论

定义

通过所有边的路径（回路）。

有向图的判定

要是 {\tt ind}_i+1={\tt outd}_i，就是起点，要是 {\tt ind}_i\neq{\tt outd}_i，那么这个点不能作为中间点。

显然一个欧拉路不能作为中间点的数量 z 必须为 0 或 2。

具体原因可以想想一笔画。

有向图的查询

当 z=0，那么我们找不到起点。

可以找一个 {\tt ind}_i\neq 0 的点，因为欧拉回路从任一点出都能回到这个点。

然后从起点 x 搜索。

我们发现直接 dfs 就可以求出路径，倒序输出 dfs 栈即可。

有向图代码

#include<bits/stdc++.h>
using namespace std;
string s;
int n,deg[2][50],st,stc,notl;
vector<int>e[50];
int dfn[1000005],cur,f[50];
void dfs(int p){
    for(;f[p]<deg[1][p];){
        int v=e[p][f[p]++];
        dfs(v);
        dfn[++cur]=v;
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        int u=s[0]-'a'+1,v=s[(int)s.size()-1]-'a'+1;
        deg[1][u]++;
        deg[0][v]++;
        e[u].push_back(v);
    }
    for(int i=1;i<=26;i++){
        if(deg[0][i]+1==deg[1][i])
            st=i,stc++;
        if(deg[0][i]!=deg[1][i])    
            notl++; 
    }
    if(notl&&!(stc==1&&notl==2))
        return cout<<"No\n",0;
    if(!st)
        for(int i=1;i<=26;i++)if(deg[0][i])
            st=i;
    dfn[++cur]=st;
    dfs(st);
    if(cur!=n+1)
        return cout<<"No\n",0;
    cout<<"Yes\n";
    for(int i=cur;i>=1;i--)
        cout<<char(dfn[i]+'a'-1)<<" ";
    return 0;
}

无向图的判定

我们发现这时 \tt deg 统一了。

首先，要是 {\tt deg}_i\bmod 2=1，那么我们认为这个点是奇点，设有 x 个，同时我们要用这个设为搜索起点。

无向图的查询

我们注意到这时就无法简单标记已经走过的边了。

考虑标记 (u,v) 和 (v,u)，直接做。

无向图代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,deg[N],st,stc,m;
vector<pair<int,int>>e[N];
int dfn[N<<2],cur,f[N];
bool vis[N];
void dfs(int p){
    for(auto v:e[p])if(!vis[v.second]){
        vis[v.second]=1;
        dfs(v.first);
        dfn[++cur]=v.first;
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        deg[u]++;
        deg[v]++;
        e[u].push_back({v,i});
        e[v].push_back({u,i});
    }
    for(int i=1;i<=n;i++)
        if(deg[i]&1)
            st=i,++stc;
    if(!(stc==0||stc==2))
        return cout<<"No\n",0;
    if(!st)
        for(int i=1;i<=n;i++)if(deg[i])
            st=i;
    dfn[++cur]=st;
    dfs(st);
    if(cur!=m+1)
        return cout<<"No\n",0;
    cout<<"Yes\n";
    // for(int i=cur;i>=1;i--)
        // cout<<dfn[i]<<" ";
    return 0;
}