欧拉回路、欧拉图及其判定
在一张图上，一条从某个点出发，经过所有的边后回到原点的路径叫做欧拉回路。有欧拉回路的图叫做欧拉图。
容易发现，欧拉图一定是联通图。它还需要满足以下条件：
- 如果是无向图，那么每个结点的度数都是偶数。
- 如果是有向图，那么每个结点的入度和出度相等。
不难理解这是判断欧拉图的充要条件。
欧拉回路算法详解
我们先判断图是否是欧拉图，然后通过 DFS 的方法来找欧拉回路。
DFS 一个点的时候，我们每次找到一条没有使用过的边，然后先 DFS 那个点，再将这条边加入答案栈中。最后将栈中的元素倒序输出即可。
为了优化复杂度，我们使用当前弧优化，不难证明时间复杂度为 $O(n + m)$。
模版提交地址：「UOJ 117」欧拉回路。
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 1e5, maxm = 4e5; |
6 | int type, n, m, deg[maxn + 3], top, st[maxm + 3]; |
7 | int tot, ter[maxm + 3], id[maxm + 3], nxt[maxm + 3], lnk[maxn + 3], cur[maxn + 3]; |
8 | bool vis[maxm + 3]; |
9 | |
10 | void add(int u, int v, int w) { |
11 | ter[++tot] = v, id[tot] = w; |
12 | nxt[tot] = lnk[u], lnk[u] = tot; |
13 | } |
14 | |
15 | void dfs(int u) { |
16 | for (int &i = cur[u], x; i; i = nxt[i]) { |
17 | if (!vis[abs(x = id[i])]) { |
18 | vis[abs(x)] = true; |
19 | dfs(ter[i]), st[++top] = x; |
20 | } |
21 | } |
22 | } |
23 | |
24 | int main() { |
25 | scanf("%d %d %d", &type, &n, &m); |
26 | type--; |
27 | for (int i = 1, u, v; i <= m; i++) { |
28 | scanf("%d %d", &u, &v); |
29 | add(u, v, i), type ? void() : add(v, u, -i); |
30 | deg[u]++, deg[v] += type ? -1 : 1; |
31 | } |
32 | bool flag = true; |
33 | for (int i = 1; i <= n; i++) { |
34 | type ? flag &= !deg[i] : flag &= ~deg[i] & 1; |
35 | } |
36 | if (!flag) { |
37 | return puts("NO"), 0; |
38 | } |
39 | for (int i = 1; i <= n; i++) { |
40 | cur[i] = lnk[i]; |
41 | } |
42 | dfs(ter[1]); |
43 | if (top != m) { |
44 | puts("NO"); |
45 | } else { |
46 | puts("YES"); |
47 | while (top) { |
48 | printf("%d%c", st[top], " \n"[top == 1]), top--; |
49 | } |
50 | } |
51 | return 0; |
52 | } |
欧拉回路算法的应用
「BZOJ 3033」太鼓达人
题目大意
给定 $n$，要求输出一个长度为 $2^n$ 的，每个位置为 $0, 1$ 的环，使得环上所有连续 $n$ 位组成的二进制数互不相同。如果有多解，输出字典序最小的。
数据范围：$n \le 11$。
思路分析
其实这题 $n \le 20$ 也是能做的。
其实这题还可以贪心，但是这里就不讲解了。
考虑将每个长度为 $n$ 的二进制数看作一条边，它连接的两个点分别是它去掉最后一位和它去掉第一位后长度为 $n - 1$ 的二进制数。然后我们在这个点数为 $2^{n - 1}$，边数为 $2^n$ 的图上跑欧拉回路即可。
注意到这题要求字典序最小的方案。于是我们注意加边顺序即可。时间复杂度 $O(2^n)$。
代码实现
1 | |
2 | |
3 | const int maxn = 11, maxm = 1 << maxn; |
4 | int n, m, tot, ter[maxm + 3], wei[maxm + 3], nxt[maxm + 3], lnk[maxm + 3], cur[maxm + 3], top, st[maxm + 3]; |
5 | bool vis[maxm + 3]; |
6 | |
7 | void add(int u, int v, int w) { |
8 | ter[++tot] = v, wei[tot] = w; |
9 | nxt[tot] = lnk[u], lnk[u] = tot; |
10 | } |
11 | |
12 | void dfs(int u) { |
13 | for (int &i = cur[u], x; i; i = nxt[i]) if (!vis[i]) { |
14 | vis[i] = true, x = wei[i]; |
15 | dfs(ter[i]), st[++top] = x; |
16 | } |
17 | } |
18 | |
19 | int main() { |
20 | scanf("%d", &n); |
21 | printf("%d ", 1 << n); |
22 | if (n == 1) { |
23 | return puts("01"), 0; |
24 | } |
25 | for (int i = 1; ~i; i--) { |
26 | for (int msk = 0; msk < 1 << (n - 1); msk++) { |
27 | add(msk + 1, ((msk * 2 + i) & ((1 << (n - 1)) - 1)) + 1, i); |
28 | } |
29 | } |
30 | for (int i = 1; i <= 1 << (n - 1); i++) { |
31 | cur[i] = lnk[i]; |
32 | } |
33 | dfs((1 << (n - 1))); |
34 | while (top) { |
35 | putchar(st[top--] + '0'); |
36 | } |
37 | puts(""); |
38 | return 0; |
39 | } |
「POI 2010」Bridges（BZOJ 2095）
题目大意
待更 ……