经过所有边一次的路径叫做欧拉路径（一笔画），若路径起点和终点相同，称之为欧拉回路

判定条件

有向图欧拉路径 一个起点（出度-入度=1），一个终点（入度-出度=1），剩余节点（出度=入度）

有向图欧拉回路  所以节点（入度=出度）

无向图欧拉路径 一个起点（度数=奇数），一个终点（度数=奇数），剩余节点（度数为偶数）

无向欧拉回路， 所有节点度数都是偶数

以上四条都建立在将有向边视为无向边后，图是连通图

【模板】欧拉路径 - 洛谷

有向图中的欧拉回路与欧拉路径

# include
# include
# include
# include
# include
 
using namespace std;
 
int nowid[100000+10];
int ru[100000+10],chu[100000+10];
int n,m;
stack<int>st;
vector<int>v[100000+10];
 
void dfs(int now)
{
 
    for(int i=nowid[now];isize();i=nowid[now])
    {
        nowid[now]=i+1;
 
        dfs(v[now][i]);
 
    }
 
    st.push(now);
}
 
int main ()
{
    cin>>n>>m;
 
    for(int i=1;i<=m;i++)
    {
        int x,y;
 
        cin>>x>>y;
 
        chu[x]++;
 
        ru[y]++;
 
        v[x].push_back(y);
 
    }
 
    for(int i=1;i<=n;i++)
    {
        sort(v[i].begin(),v[i].end());
 
    }
 
    int b=1,e,cntb=0,cnte=0;
    int cnt=0,flag=0;
 
 
    for(int i=1;i<=n;i++)
    {
 
        if(ru[i]!=chu[i])
        {
            flag=1;
        }
 
        if(chu[i]-ru[i]==1)
        {
            cntb++;
 
            b=i;
 
 
        }
        else if(ru[i]-chu[i]==1)
        {
            cnte++;
 
 
        }
        else if(ru[i]==chu[i])
        {
            cnt++;
        }
 
 
    }
 
    if(!(cnt==n-2&&cntb==1&&cnte==1)&&flag)
    {
        cout<<"No";
 
 
        return 0;
    }
 
    dfs(b);
 
    while(!st.empty())
    {
        cout<top()<<" ";
 
        st.pop();
    }
 
    return  0;
 
}

无序字母对 - 洛谷

无向图的，没保证连通性，还需要判断连通性，但貌似本题不判断也可以。

另外无序字母对不相同说明标记一次边就够了

# include
# include
# include
# include
# include
 
using namespace std;
 
vector<int>v[1000];
int du[1000];
bool mp[1000][1000];
stack<int>st;
 
void dfs(int now)
{
    for(auto it:v[now])
    {
        if(!mp[it][now])
        {
            mp[it][now]=1;
            mp[now][it]=1;
 
            dfs(it);
        }
    }
    st.push(now);
}
int main ()
{
 
     int t;
 
     cin>>t;
 
     while(t--)
     {
         string s;
 
         cin>>s;
 
         du[s[0]]++;
         du[s[1]]++;
         v[s[0]].push_back(s[1]);
         v[s[1]].push_back(s[0]);
 
     }
 
     for(int i=1;i<=200;i++)
     {
         sort(v[i].begin(),v[i].end());
 
     }
     int cnt=0;
     int b=999;
     for(int i=1;i<=200;i++)
     {
         if(du[i]&1)
            {
                cnt++;
                b=min(b,i);
            }
 
     }
 
 
     if(cnt==0)
     {
         b=999;
 
         for(int i=1;i<=200;i++)
         {
             if(du[i])
             {
                 b=i;
                 break;
 
             }
         }
         if(b==999)
         {
             cout<<"No Solution";
 
         }
         else
 
         {
              dfs(b);
 
             while(!st.empty())
             {
                 cout<<(char)(st.top());
 
                 st.pop();
             }
         }
     }
     else
     {
         if(cnt==2)
         {
             dfs(b);
 
             while(!st.empty())
             {
                 cout<<(char)(st.top());
 
                st.pop();
             }
         }
         else
         {
             cout<<"No Solution";
 
             return 0;
         }
     }
 
 
 
    return  0;
 
}

[USACO3.3]骑马修栅栏 Riding the Fences - 洛谷

和上一题不同的是，本题无向边多个

#include
#include
#include
#include
 
using namespace std;
 
int edge[600][600];
 
int n;
int du[1000];
 
stack<int>st;
 
void dfs(int now)
{
    for(int i=1;i<=500;i++)
    {
        if(edge[now][i])
        {
            edge[now][i]--;
 
            edge[i][now]--;
 
            dfs(i);
 
        }
    }
 
    st.push(now);
 
}
int main()
{
 
    cin>>n;
 
    for(int i=1; i<=n; i++)
    {
        int x,y;
 
        cin>>x>>y;
 
        edge[x][y]++;
 
        edge[y][x]++;
 
 
        du[x]++;
 
        du[y]++;
 
 
    }
 
    for(int i=1;i<=500;i++)
    {
        if(du[i]&1)
        {
            dfs(i);
 
 
 
            while(!st.empty())
            {
                cout<top()<<'\n';
 
                st.pop();
            }
 
            return 0;
 
        }
    }
    
    for(int i=1;i<=500;i++)
    {
        
         if(du[i])
        {
            dfs(i);
 
 
 
            while(!st.empty())
            {
                cout<top()<<'\n';
 
                st.pop();
            }
 
            return 0;
 
        }
        
    }
 
    return 0;
}