欧拉路

莫名其妙之前总结的不见了,只好copy一下蔡大佬的嘻嘻

基本概念

欧拉图: 能够没有重复地一次遍历所有边的图。(必须是连通图)

欧拉路: 上述遍历的路径就是欧拉路。

欧拉回路: 若欧拉路是闭合的(一个圈,从起点开始遍历最终又回到起点),则为欧拉回路。

无向图G有欧拉路径的充要条件

  1. G是连通图
  2. G中奇顶点(连接边的数量为奇数)的数量等于0或2.

无向图G有欧拉回路的充要条件

  1. G是连通图
  2. G中每个顶点都是偶顶点

有向图G有欧拉路径的充要条件

  1. G是连通图
  2. u的出度比入度大1,v的出度比入度小1,其他所有点出度和入度相同。(u为起点,v为终点)

有向图G有欧拉回路的充要条件

  1. G是连通图
  2. G中每个顶点的出度等于入度

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int G[maxn][maxn];
int deg[maxn][maxn];
vector<int> Ans;
void init() { clr(G, 0), clr(deg, 0); }
void addedge(int u, int v) { deg[u]++, deg[v]++, G[u][v]++, G[v][u]++; }
void Fleury(int s)
{
for (int i = 0; i < n; i++)
if (G[s][i])
{
G[s][i]--, G[i][s]--;
Fleury(i);
}
Ans.pb(s);
}