[笔记]欧拉图

定义

• 欧拉路径是每条边恰好经过一次的路径；存在欧拉路径的图是半欧拉图。
• 欧拉回路是每条边恰好经过一次的回路；存在欧拉回路的图是欧拉图。

判定

• 无向图是欧拉图\(\iff\)非零度节点连通，所有节点度数为偶。此时起点可以选任意节点。
• 无向图是半欧拉图\(\iff\)非零度节点连通，恰有\(2\)个节点度数为奇。此时起点可以选两个奇度节点之一。
• 有向图是欧拉图\(\iff\)非零度节点强连通，每个节点出入度相等。此时起点可以选任意节点。
• 有向图是半欧拉图\(\iff\)非零度节点弱连通，至多一个顶点出度\(-\)入度\(=1\)，至多一个顶点入度\(-\)出度\(=1\)，其他节点出入度相等。此时起点是那个出度\(-\)入度\(=1\)的节点。

例题：

• 有向图：UVA10129 单词 Play on Words ~ 题解
• 无向图：P1333 瑞瑞的木棍 ~ 题解

输出

下文中，将要输出的内容存入栈st中，输出时逐个弹栈即可；p初始全为\(0\)。

由于要求按最小字典序输出，所以需要对出边从小到大排序，因此使用了邻接表存储。

输出途径点（有向图） - P7771 【模板】欧拉路径

void dfs(int u){for(int i=p[u];i<out[u];i=p[u]){p[u]++;dfs(G[u][i]);}st.push(u);
}

输出途径点（无向图） - P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

void dfs(int u){for(int i=p[u];i<out[u];i=p[u]){p[u]++;if(cnt[u][v]) cnt[u][v]--,cnt[v][u]--,dfs(G[u][i]);}st.push(u);
}

输出途径边（有向图） - P1127 词链

void dfs(int u){for(int i=p[u];i<out[u];i=p[u]){p[u]++;dfs(G[u][i].to);st.push(G[u][i].id);}
}

输出途径边（无向图） - [暂无]

void dfs(int u){for(int i=p[u];i<out[u];i=p[u]){p[u]++;if(cnt[u][v]) cnt[u][v]--,cnt[v][u]--,dfs(G[u][i].to);st.push(G[u][i].id);}
}