学习笔记

欧拉回路学习笔记


下面的内容主要是是搬运的陈通的集训队论文,可能会有点私货和代码(大雾)。
论文链接

基本概念

定义1.1:图 $G$ 中经过每一条边恰一次回路称为欧拉回路经过每条边恰一次的路径称为欧拉路径
定义1.2:存在欧拉回路的图称为欧拉图,存在欧拉路径但不存在欧拉回路的图称为半欧拉图

欧拉图的判定

无向欧拉图

定理2.1:无孤立点的无向图 $G$ 为欧拉图,当且仅当图 $G$ 连通所有顶点的度都是偶数
定理2.2:如果无向连通图有 $2k$ 个奇顶点,则图 $G$ 可以用 $k$ 条路径将图 $G$ 的每一条边经过一次,且至少要使用 $k$ 条路径。
定理2.3:无孤立点的无向图 $G$ 为半欧拉图,当且仅当图 $G$ 连通且 $G$ 的奇顶点数为 $2$。此时两个奇顶点分别为欧拉路径的起点和终点。

有向欧拉图

定理2.4:无孤立点的有向图 $G$ 为欧拉图,当且仅当图 $G$ 弱连通所有顶点的入度等于出度
定理2.5:对于连通有向图,所有顶点入度与出度差的绝对值之和为 $2k$,则图 $G$ 可以用 $k$ 条路径将图 $G$ 的每一条边经过一次,且至少要使用 $k$ 条路径。
定理2.6:无孤立点的有向图 $G$ 为半欧拉图,当且仅当图 $G$ 弱连通,且恰有一个顶点 $u$ 入度比出度小 $1$,一个顶点 $v$ 入度比出度大 $1$,其余顶点入度等于出度,。此时存在 $u$ 作为起点,$v$ 作为终点的欧拉路径。

欧拉回路的生成

以下算法和代码都是针对无向图的解决方案,有向图只需要稍加修改即可。

Fluery算法

咕咕咕,回头再更


update

貌似是个时间复杂度不够优秀、代码又难写、又冷门的算法,被下面要介绍的算法吊打的那种。
emmmm代码我也没从网上找到能看的模板,既然冷门也不想自己码自己yy了,所以干脆介绍一下算法流程就完事吧,毕竟没理由写这个算法QAQ。

算法流程

记欧拉回路为 $p$。
1.任选图 $G$ 中的一个顶点 $v_0$,令 $p_0:v_-$。
2.若当前路径只有一条未加入路径的出边 $(v_k,u)$,则令 $v_{k+1} = u$;否则找到一条对于图 $G-G_p$ 不是桥的边,令 $v_k=u$,删去这条边,将 $v_{k+1}$ 加入路径。
3.(2)无法执行时结束,此时 $p_m$ 即为一条欧拉回路。

解释

关于第二步为什么不能优先走桥,其实结合一下定理就不难理解。我们已经存储了一条路径了,我们需要从剩下的未删除的图中找到一条和当前路径首尾相接的欧拉路径来拼出一条欧拉回路。前面有提到只有两个点的度数为奇数无向连通图一定存在欧拉路径,那么未删除的图中肯定有两个点的度数为奇数,这个很好满足,显然,从图中删除一条路径,只改变了路径两个端点度数的奇偶性,而且存在欧拉回路的无向图一定满足所有点的度数都是偶数;那么此时只要满足连通就可以了,不难发现只要选桥,未删除的图就一定是联通的。

Hierholzer

那就开始介绍重头戏 $\text{Hierholzer}$ 算法吧。
该算法时间复杂度是线性的,极为常用,十分优秀的算法。
同时如果从一个合法的起点开始,也可以求出欧拉路径。

算法流程

1.任取图中一个顶点 $v_0$ ,将 $v_0$ 加入栈 $S$。
2.记栈顶元素为 $u$,若 $u$ 不存在未访问的出边,则将 $u$ 插入路径 $P$ 的前端。否则任选一条未访问的出边 $(u,v)$,将 $v$ 加入栈 $S$。
3.重复(2)直到栈 $S$ 为空,此时 $P$ 即为所求的欧拉回路。
注意要倒序输出存储路径的数组。

解释

这个算法的实质上是找到若干条回路拼接到一起。
不难发现在一张欧拉图上,联系一下欧拉图的特点,从任意起点开始能走就走,走到无路可走为止一定是回到了起点构成了一条回路。但是这条回路未必经过了所有边,怎么办呢?把栈顶弹出去,找到栈里还可以继续往外走的点,重复执行以上操作,就可以再找到回路。若干无重复边的回路显然是可以通过点拼接在一起的。

代码实现

void dfs(int u) {
    for (int &head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (used[e]) continue;
        used[e] = used[e ^ 1] = true;
        dfs(v);
    }
    ans[++tail] = u;
}

谈谈有向图吧,其实是一样的,把代码里的删除双向边改成删除单向边就可以了。

模板题1

uoj117

Source Code
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int MAXN = 5e5 + 7;
struct Edge {
    int t, next;
} edge[MAXN << 1];
int n, m;
int head[MAXN], cnt = 1;
int deg[MAXN];
int seq[MAXN], tail;
bool used[MAXN];
inline int pos(const int &x) {return (x >> 1) * (x & 1 ? -1 : 1);}
void add(const int &u, const int &v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
namespace solve1 {
    void dfs(int u) {
        for (int &e = head[u]; e; e = edge[e].next) {
            int v = edge[e].t, id = pos(e);
            if (used[e]) continue;
            used[e] = used[e ^ 1] = true;
            dfs(v);
            seq[++tail] = id;
        }
    }
    void solve() {
        scanf("%d %d", &n, &m);
        int u, v;
        while (m--) {
            scanf("%d %d", &u, &v);
            add(u, v);
            add(v, u);
            deg[u] ^= 1, deg[v] ^= 1;
        }
        for (int i = 1; i <= n; i++) {
            if (deg[i]) {
                printf("NO");
                exit(0);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (head[i]) {
                dfs(i);
                break;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (head[i]) {
                printf("NO\n");
                exit(0);
            }
        }
        printf("YES\n");
        for (int i = tail; i; i--) {
            printf("%d ", seq[i]);
        }
    }
}
namespace solve2 {
    void dfs(int u) {
        for (int &e = head[u]; e; e = edge[e].next) {
            int v = edge[e].t, id = e - 1;
            if (used[e]) continue;
            used[e] = true;
            dfs(v);
            seq[++tail] = id;
        }
    }
    void solve() {
        scanf("%d %d", &n, &m);
        int u, v;
        while (m--) {
            scanf("%d %d", &u, &v);
            add(u, v);
            deg[u]++, deg[v]--;
        }
        for (int i = 1; i <= n; i++) {
            if (deg[i]) {
                printf("NO\n");
                exit(0);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (head[i]) {
                dfs(i);
                break;
            }
        }
        for (int i = 1; i <= n; i++) {
            if(head[i]) {
                printf("NO\n");
                exit(0);
            }
        }
        printf("YES\n");
        while (tail) {
            printf("%d ", seq[tail--]);
        }
    }
}
int main(int argc, char *argv[]) {
    int type;
    scanf("%d", &type);
    if (type == 1) solve1::solve();
    else solve2::solve();
    return 0;
}

模板题2

LuoguP2731
这个也不算裸的模板吧,因为有最小字典序这个限制,而且求的也不一定是欧拉回路,可能是欧拉路径,需要判断一下点的度数,选一个合适的起点。
这道题数据范围很小,邻接矩阵从小到大遍历出边就可以过。
想想数据范围大点怎么办?把出边排个序呗。用 $vector$ 写应该也挺方便的。
原理的话,结合一下 $Hierholzer$ 算法的本质,是在找回路拼在一起。那么如果排过序,就是先找到一个字典序最小的回路,然后再回溯,继续拓展仍有未访问边的点,继续找字典序最小的回路。
更直观感性地解释一下就是:
栈先进后出,字典序小的先进去了,那么我们是反向往回路加边的,那就求的是最小字典序。

Source Code
#include 
#include 
#include 
#include 
#include 
#include 
const int MAXN = 2e3 + 7;
int edge[MAXN][MAXN];
int seq[MAXN], tail, deg[MAXN];
int n;
void dfs(int u) {
    for (int i = 1; i <= n; i++) {
        if (edge[u][i]) {
            edge[u][i]--;
            edge[i][u]--;
            dfs(i);
        }
    }
    seq[++tail] = u;
}
int main(int argc, char *argv[]) {
    int m,  start = INT_MAX;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        edge[u][v]++;
        edge[v][u]++;
        deg[u]++, deg[v]++;
        n = std::max(n, std::max(u, v));
        start = std::min(start, std::min(u, v));
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i] & 1) {
            start = i;
            break;
        }
    }
    dfs(start);
    for (int i = tail; i; i--) {
        printf("%d\n", seq[i]);
    }
    return 0;
}

欧拉图相关性质

定理4.1

对于任意无相连通图 $G$,一定存在回路使得每条边经过恰好两次,存在回路使得每条边的两个方向各经过一次。
前者把这张图每条边建两次就好了,显然是一张无向欧拉图;后者每条边正反都建一次,显然是一张无向欧拉图。既然是欧拉图,就都存在欧拉回路。

例题4.1

题目链接

Codeforces Round #407(Div.1).B

题意

给定一张无向图(不保证联通),总共有 $n$ 个节点,$m$ 条路径,要求其中 $m-2 $条路径走两遍,剩下 $2$ 条路径仅走一遍,问不同的路径总数有多少,如果仅走一遍的两条边不同则将这两条路径视为不同。
不保证没有重边与自环,每个点最多有一个自环。
$1 \leq n,\ m \leq 10^6$。

解法

直接套用上面说过的结论就好了。题意转化一下就是说让原图 $G$ 的每条边建两遍,那么显然是一张欧拉回路。要求删去两条边之后这张图存在欧拉路径。
既然存在欧拉路径,那么必然存在两个或者零个奇度点。删去一条边会使得两个端点的度数减一,那么只存在以下三种合法的删边方式。
1.删除两条自环(删除后为欧拉图)。
2.删除两条有公共点的边(删除后为半欧拉图)。
3.删除一条自环与一条边(删除后为半欧拉图)。
那么分别统计方案就可以了。
注意这张图不一定连通,存在无解的情况。

Source Code

#include 
#include 
#include 
#include 
const int MAXN = 1e6 + 7;
int f[MAXN], h[MAXN], self[MAXN];
int deg[MAXN], my, es;
int tot, t2;
struct Edge {
    int t, next;
} edge[MAXN << 1];
int head[MAXN], cnt;
bool vis[MAXN];
long long ans;
void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
void dfs(int u) {
    tot += deg[u];
    t2 += self[u];
    vis[u] = true;
    ans += (1LL * deg[u] * (deg[u] - 1LL) / 2LL);
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (!vis[v]) dfs(v);
    }
}
int main(int argc, char *argv[]) {
    int n, m, r;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        if (u == v) my++, self[u]++;
        else deg[u]++, deg[v]++, es++, add(u, v), add(v, u);
    }
    ans = 1LL * es * my + 1LL * (1LL * my * (my - 1)) / 2;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && deg[i]) {dfs(i); break;}
    }
    if (tot != es * 2) ans = 0;
    if (t2 != my) ans = 0;
    printf("%lld\n", tot == es * 2 ? ans : 0);
    return 0;
}

定理4.2

对于无向图 $G$,所有顶点的度数都是偶数等价于图 $G$ 有圈分解。圈分解即为用若干个圈(不重复经过顶点的回路)使图 $G$ 的每一条边恰好经过一次。
证明略,详见论文中定理2.1的证明。

例题

题目链接

bzoj3706

题意

题目说的很清楚了,没有什么花里胡哨的障眼法。

解法

首先很明确的一点是如果有解,那么黑边一定被回路走了奇数次,白边一定是偶数次。然后又没限制不可以走重边,所以不难想到白边其实无所谓,只要被改变了就再走回去就好了,因为走偶数次就相当于没走(被修改了两次)。但是黑边只能走奇数次。结合上述定理,不难得出所有点的黑边度数都为偶数是才有解(否则不存在圈分解)。
进一步,我们如何求出最小操作次数呢?答案显然是包含黑边的连通块数。不难发现如果有解,那么把所有的黑边拿出来构成一张新的图 $G'$,这张图包含若干连通块,这些连通块都存在欧拉回路。至于白边,显然可以走两遍来消除影响。说白了就是黑边走一次,白边走两次。
那么有修改怎么办呢?很显然改一条边就好了。
具体实现的时候并查集维护一下所有边的连通性,然后记录一下所有点的黑边度数、当前的答案、黑边奇度点的个数。

Source Code

#include 
#include 
#include 
#include 
#include 
const int MAXN = 1e6 + 7;
int n, m, q;
int f[MAXN], sum[MAXN], d[MAXN], ans, cnt;
int from[MAXN], to[MAXN];
bool col[MAXN];
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
void change(int pos, int r, int type) {
    sum[r] += type;
    if (type == 1 && sum[r] == 1) ans++;
    else if (type == -1 && !sum[r]) ans--;
    d[from[pos]] += type, d[to[pos]] += type;
    if (d[from[pos]] & 1) cnt++; else cnt--;
    if (d[to[pos]] & 1) cnt++; else cnt--;
}
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", from + i, to + i, col + i);
        int u = find(from[i]), v = find(to[i]);
        if (u != v) {
            f[v] = u;
            if (sum[u] && sum[v]) ans--;
            sum[u] += sum[v];
        }
        if (col[i]) change(i, u, 1);
        else if (u != v && sum[u] && sum[v]) ans--;
    }
    scanf("%d", &q);
    int opt, pos;
    while (q--) {
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d", &pos);
            pos++;
            col[pos] ^= 1;
            if (col[pos]) change(pos, find(from[pos]), 1);
            else change(pos, find(from[pos]), -1);
        } else {
            printf("%d\n", cnt ? -1 : ans);
        }
    }
    return 0;
}

定理4.3

对于不存在欧拉回路的图 $G$,若最少用 $a$ 条路径将图 $G$ 的每一条边经过一次,若最少在图 $G$ 中加入 $b$ 条有向边使之成为欧拉图,则 $a$ 一定等于 $b$。
证明和定理2.2的证明相似,不是很难。

例题4.3

题目链接

VK Cup 2012 Finals practice Session. C

解法

如果从构造加边方案入手就会很自闭很麻烦。根据定理4.3把问题转化成这张图可以被多少条路径才能使得每一条边恰好被经过一次。
1.每有一对奇度点,就会有一条路径。
2.每个不存在奇度点的连通分量,都存在欧拉回路。
那么如果记奇度点个数为 $a$,不存在奇度点的连通分量(不考虑除 $1$ 以外的孤立点,因为边与其相连)个数为 $b$ 的话,答案就是 $\frac{a}{2}+b$。
需要特别注意以下三点:
1.如果原图为欧拉图的话答案为 $0$;
2.如果点 $1$ 为孤立点,也要算作一个不含奇度点的连通分量。
3.不处理除点 $1$ 外的孤立点。

Source Code

#include 
#include 
#include 
#include 
#include 
const int MAXN = 1e6 + 7;
struct Edge {
    int t, next;
} edge[MAXN << 1];
int n, m;
int head[MAXN], cnt;
int ans, deg[MAXN], odd, block;
bool vis[MAXN], start[MAXN];
void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
bool dfs(int u) {
    vis[u] = true;
    bool flag = (deg[u] & 1) ^ 1;
    odd += !flag;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (!vis[v]) flag &= dfs(v);
    }
    return flag;
}
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &m);
    int u, v;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &u, &v);
        deg[u]++, deg[v]++;
        start[u] = start[v] = true;
        if (u == v) continue;
        add(u, v);
        add(v, u);
    }
    int cnt = 0;
    start[1] = true;
    for (int i = 1; i <= n; i++) {
        if (start[i] && !vis[i]) {block += dfs(i); cnt++;}
    }
    if (cnt == 1 && !odd) ans = 0;
    else ans = (odd / 2 + block);
    printf("%d\n", ans);
    return 0;
}

De Brujin序列

问题5.1

求出一个 $2^n$ 位环形 $0/1$ 串,满足所有 $2^n$ 个长度为 $n$ 的子串恰为所有 $2^n$ 个的 $n$ 位的 $0/1$ 序列。

解法:

比较容易想到的做法是把所有的子串看做一个点,求出哈密尔顿回路。但是哈密尔顿回路是一个 $NPC$ 问题,很难求出。
所以我们把子串看成边,子串 $x_1x_2...x_n$ 这条边连接 $(x_1x_2...x_{n-1},x_2x_3...x_{n})$。
显然每个点的出度和入度都是 $2$,那么显然是一张欧拉图,求一下欧拉回路就可以了。
拓展一下的话,不只是二进制,可以求 $k$ 进制下的长度为 $n^k$ 的 满足以上条件的串。这个叫做 $\text{De Brujin}$ 序列。

例题5.1

题目链接

poj1780

题意

求十进制下长度为 $n$ 的串的字典序最小的 $\text{De Bruijin}$ 序列。

题解

按照上面给出的构造方法建好图跑一遍 $Hierholzer$ 算法就好了。
但是求的是字典序最小的解,然后邻接表是会先遍历后加入的边的,所以从大大小枚举子串加边。
还有两点要注意,不要写递归,会爆栈,要写栈;注意常数优化,尽可能不要使用 $STL$,$poj$ 的优化很差。

Source Code

#include 
#include 
#include 
#include 
#include 
#include 
const int MAXN = 1100000;
struct Edge {
    int t, next;
} edge[MAXN << 1];
int head[MAXN], cnt;
int p10[121], n;
int seq[MAXN], tail;
int stack[MAXN], top;
void init() {
    cnt = 0; tail = 0;
    memset(head, 0, sizeof head);
}
void add(int u, int v) {
    cnt++;
    edge[cnt].t = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
void solve(int s) {
    stack[++top] = s;
    while (top) {
        int u = stack[top], &e = head[u];
        if (e) stack[++top] = edge[e].t, e = edge[e].next;
        else seq[++tail] = u, top--;
    }
}
int main(int argc, char *argv[]) {
    p10[0] = 1;
    for (int i = 1; i <= 6; i++) p10[i] = p10[i - 1] * 10;
    int n;
    while (1) {
        scanf("%d", &n);
        if (!n) return 0;
        if (n == 1) {printf("0123456789\n"); continue;}
        init();
        for (int i = p10[n] - 1; i; i--) {
            add(i / 10, i % p10[n - 1]);
        }
        solve(0);
        for (int i = 1; i < n; i++) printf("0");
        for (int i = tail; i; i--) {
            printf("%d", seq[i] % 10);
        }
        printf("\n");
    }
    return 0;
}

欧拉图计数

问题 6.1

求包含 $n$ 个点的所有点度数为偶数的有标号无向连通图个数。

解法

设 $s_n$ 为所求的答案。考虑除去 $n$ 号点和与其相连的边,那么剩下的图中必然包含偶数个奇顶点。
也就是说 $n$ 号点必然与偶数个奇顶点相连。显然任意一个无向图的奇顶点的个数为偶数,那么答案就是 $n-1$ 个点的无向简单图的个数。
所以就有
$$s_n = 2^{C_{n-1}^2}$$

问题 6.2

求 $n$ 个点的有标号简单连通无向欧拉图的个数。

解法

记 $f_n$ 为所求的答案。
同时处理连通和度数两方面的约束比较困难,但是我们已经解决了度数的问题。接下来利用容斥原理解决联通这一限制。
显然,$f_n$ 为 $s_n$ 减去不连通的方案数,而不连通的方案数可以通过枚举 $1$ 号点所在连通分量大小计算。
当连通分量大小为 $i$ 时,该连通分量内点的集合有 $C_{n-1}^{i-1}$ 种不同的组合方式,这些点之间的连边方法有 $f_i$ 种,剩余点之间就不需要保证连通了,有 $s_{n-1}$ 种。
所以有如下公式
$$f_n = s_n - \sum_{i = 1}^{n - 1}C_{n-1}^{i-1}f_is_{n-i}$$
裸的写法时间复杂度是 $O(n^2)$ 的,可以用分治 $\text{FFT}$ 或者多项式求逆优化到一个或者两个 $log$(具体我不会2333)。

结束咯,实在是写不动了

发表评论

电子邮件地址不会被公开。 必填项已用*标注