欧拉路径和欧拉回路

首先，无论是有向图还是无向图，存在欧拉路径和欧拉回路的必要条件是，所有的边都是连通的

定义（口胡的）：

欧拉路径 ： 在一张图中，存在一个经过所有边的路径，并且经过每条边的次数有且仅有一次。

欧拉回路: 如果一个回路是欧拉路径，则称该回路为欧拉回路

一、无向图

• 存在欧拉路径的充分必要条件：度数为奇数的点只能有 $0$ 或 $2$ 个。
• 存在欧拉回路的充分必要条件：度数为奇数的点只能为 $0$ 个。（点的度数一定都是偶数）

二、有向图

• 存在欧拉路径的充分必要条件（两者满足一种即可）：
• 所有点的出度均等于入度；
• 除了两个点之外，其余所有点的入度等于出度，剩余的两个点：一个点满足 “出度 = 入度 + 1” （起点） ， 另一个点满足 “入度 = 出度 + 1 ” （终点）。
• 存在欧拉回路的充分必要条件：所有的点的出度均等于入度。

值得注意的是，如果有自环的情况存在，为了保证算法的复杂度，利用搜完即删的方法删边

这里仅给出有向图中求解欧拉路径的代码，毕竟这系列代码思路基本相同

code

//cnt 代表欧拉路径中的节点个数，如果cnt != n 说明该图不连通，不存在欧拉路径
void dfs(int u )
    {
        for(int i = 0 ; i < 26 ; i++ )
        {
            if(g[u][i])
            {
                g[u][i]-- ;
                dfs(i ) ;
                ++cnt ;
            }
        }
    }
    for(int i = 0 ; i < 26 ; i++ )
        {
            if(rd[i] != cd[i])
            {
                if(rd[i] == cd[i] + 1 )  vz++ ;
                else if(cd[i] == rd[i] + 1 ) uz++ ;
                else
                {
                    pd = false ;
                    break ;
                }
            }
        }

        if(!(!vz && !uz || (uz == 1 && vz == 1))) pd = false;
        int now = 0 ;
        while(! cd[now] )   now++ ;
        for(int i = 0 ; i < 26 ; i++ )
        {
            if(cd[i] == rd[i] + 1)
            {
                now = i ;
                break ;
            }
        }
        dfs(now ) ;
        if(cnt < n )    pd = false ;

邻接表存图版

void dfs(int u)
{
    for (int &i = h[u]; ~i;)
    {
        if (used[i])
        {
            i = ed[i].nxt ;//删边
            continue;
        }
        used[i] = true;//标记是否使用过
        if (type == 1) used[i ^ 1] = true;

        int t;

        if (type == 1)
        {
            t = i / 2 + 1;
            if (i & 1) t = -t;
        }
        else t = i + 1;

        int j = ed[i].to ;
        i = ed[i].nxt ;

        dfs(j);
        ans[ ++ cnt] = t;//经过边的编号，负数则为反向边
    }
}

注：$AcWing$ 算法提高课笔记