浅谈欧拉路径，欧拉回路

引入

前有哈密顿路径，表示经过每个点恰好一次，现有欧拉路径，表示经过每条边恰好一次。

许多题目重要的是建模，往往最浅的建模就是点之间的连边，表示可以到达。如果说需要满足到达每个点一次，这就变成了 $\tt NPC$ 问题。但是我们往往可以将一个信息拆分成若干个信息，变成边之间的关系，这样就有多项式复杂度的解法，同样这个是可以求方案的。

本篇会向读者介绍欧拉路径和欧拉回路以及其判定方法，还有常用的套路。

欧拉图

具有欧拉回路的图叫欧拉图，如果只有欧拉路径就叫做半欧拉图。

欧拉路径

定义：

经过每条边恰好一次，起点和终点不一定相同。

无向图

每个点的度数都是偶数，或者只有两个节点度数是奇数。

有向图

设一个点的权值 $v_i$ 表示其出度减去入度。

那么存在的欧拉路径的条件是 $v_i = 0$ 或者同时存在一个 $v_i = 1, v_j = -1, i \ne j$。

欧拉回路

定义

经过每条边恰好一次，起点和终点相同。

无向图

每个点的度数都是偶数。

有向图

设一个点的权值 $v_i$ 表示其出度减去入度。

那么存在的欧拉路径的条件是 $v_i = 0$。

具体实现

如果说对于一条路径起点和终点是不同的，作为开始的节点需要是出度较大的节点。

我们考虑直接进行暴力 $\tt dfs$，每次删除一条边。在遍历完其相邻的所有点之后将当前点加入答案。

复杂度是 $O(n + m)$ 的。

1
2
3
4
5
6
7
void dfs(int p) {
    while(!vc[p].empty()) {
        int v = vc[p].back(); vc[p].pop_back();
        dfs(v);
    }
    ans[++ ed] = p;
}

为什么要最后加入当前点呢？

如果说出现环的情况，而且我们对于当前点 $u$ 并不是第一次遍历环，那么直接记录答案显然是不行的。

但是我们可以先走这个环，再走链。这种时候就可以考虑最后加入点，这样就是倒着走，环并不会影响答案。

读者可以尝试画画图，因为笔者个人博客从来不放图，请见谅。

因为这样我们的答案是反着的，所以我们可以翻转一下数组。

之后的答案都指翻转数组之后的。

套路

字典序要求

  • 字典序最小：贪心走最小的点即可。
  • 字典序最大：贪心走最大的点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

namespace Legendgod {

namespace Read {
//    #define Fread
    #ifdef Fread
    const int Siz = (1 << 21) + 5;
    char buf[Siz], *iS, *iT;
    #define gc() (iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iT == iS ? EOF : *iS ++ ) : *iS ++)
    #define getchar gc
    #endif // Fread

    template <typename T>
    void r1(T &x) {
        x = 0; int f(1); char c(getchar());
        for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
        for(; isdigit(c); c = getchar()) x = (x * 10) + (c ^ 48);
        x *= f;
    }
    template <typename T, typename...Args>
    void r1(T &x, Args&...arg) {
        r1(x), r1(arg...);
    }

}

using namespace Read;

const int maxn = 2e5 + 5;

struct Graph {
    vector<int> vc[maxn];
    int del[maxn];
    void add(int u,int v) {
        vc[u].push_back(v);
    }
}G;

int n, m, deg[maxn];
int st[maxn], ed(0);

void dfs(int p) {
    for(int &i = G.del[p]; i < (int)G.vc[p].size(); ) {
        int to = G.vc[p][i];
        ++ i;
        dfs(to);
    }
    st[++ ed] = p;
}

signed main() {
    int i, j;
    r1(n, m);
    for(i = 1; i <= m; ++ i) {
        int u, v;
        r1(u, v), G.add(u, v);
        -- deg[v], ++ deg[u];
    }
    int sum(0), ps(0);
    for(i = 1; i <= n; ++ i) {
        if(deg[i] == 1) ++ sum, ps = i;
        else if(deg[i] == -1) ++ sum;
        else if(deg[i] != 0) return puts("No"), 0;
    }
    if(sum > 2) return puts("No"), 0;
    if(ps == 0) ps = 1;
    for(i = 1; i <= n; ++ i) sort(G.vc[i].begin(), G.vc[i].end());
    dfs(ps);
    if(ed - 1 != m) return puts("No"), 0;
    for(i = ed; i >= 1; -- i) printf("%d%c", st[i], " \n"[i == 1]);
    return 0;
}

}

signed main() { return Legendgod::main(), 0; }

拆点成边

例题1

求一个最短的字符串，使得其包含所有的 $n$ 位 $k$ 进制数。

最好的方法就是考虑每次增加一个字符，但是显然直接来做是不方便的。

可能会考虑对于每一个 $k$ 进制数，其能到达的数连边加边权，边权是需要的字符数。

这样转换只能用 $2^x$ 指数级暴力，状压来写。

我们考虑将每个 $n$ 位数，拆分成两个 $n - 1$ 位的数。 $(a_1a_2a_3a_4a_5\dots a_{n - 1})_k \to (a_2 a_3 a_4 a_5 a_6 \dots a_n)_k$ 进行连边。

这样拆出来的每条边都需要经过恰好一次，每次正好是增加一个字符，可以保证答案最小。

如何保证有解？

显然对于最终的一个字符串肯定能拆分成若干个上述形式的 $n - 1$ 位的数。

因为字符串长度是最小的，所以两个 $n - 1$ 位的数之间的边不会重复经过。

别忘了是欧拉路径，所以经过多次同一个点是合法的。

更好的理解

考虑最终答案字符串的更新过程，也就是每次选取当前区间的 $n$ 的字符进行匹配。

那么显然对于上一个区间更新到这个区间本质上就是$\large\color{red}\text{去掉上一个字符，加上当前的字符}$。

显然对于一个状态我们并不需要长度为 $n$ 的区间，而是长度为 $n- 1$ 的区间。

那么相同的部分就是中间的 $n - 2$ 个字符，那么上述的东西可以看做一个状态的转移，从一个 $n - 1$ 长度的区间转移到另外一个长度为 $n - 1$ 的区间。总共有多少个可以转移的区间呢？

对于每一个长度为 $n$ 的数，正好意味着这样的转移。

之后直接进行跑欧拉回路即可。

例题2

设一种拆分为对于一个字符串取出其所有长度为 $k$ 连续子串。

给定 $n$ 个长度为 $k$ 的字符串，问能否复原一个长度为 $n + k - 1$ 的字符串，构造任意方案即可。

考虑一下直接将字符串作为点，还是一个哈密顿回路。

那么看到这个问题我们不妨将一个长度为 $k$ 的字符串变成两个长度为 $k - 1$ 的字符串进行连边。

同样也可以考虑最终字符串的转移，对于每个长度为 $k$ 的区间可以拆分成两个长度为 $k - 1$ 的区间。

每个字符串意味着这样的转移。

进行欧拉路径的处理即可。

  • 特判图不连通。

Best 定理

限制

$\huge\color{red}\text{必须是欧拉图}$！！！

前置：矩阵树定理

求一张图的生成树个数。

设 $D(G)$ 是度数矩阵，$A(G)$ 是邻接矩阵，拉普拉斯矩阵 $L(G) = D(G) - A(G)$。

重边也可以计算，但是自环不计邻接矩阵但是计 入度数。

然后随意去掉行号和列号相同的一行一列，得到的就是 $n - 1$ 阶主子式，求出其行列式就是方案数。

有向图

  • 如果说是求根向树形图，那么度数矩阵就是出度。

  • 如果说是求叶向树形图，那么度数矩阵就是入度。

  • 任意相同的行和列得到的 $n - 1$ 阶主子式。

  • 如果求这样的树形图的所有生成树，对于每一个根进行计数即可。

其实上面那个东西的行列式其实就是 $\sum_{T \in Tree} \prod_{w \in Edge} w$。

也就是每个生成树的边权的乘积。

所以如果要求上面的那个东西，将邻接矩阵 $A_{i, j}$ 定义成 $i \to j$ 的边权即可。

具体部分

如果图 $G$ 是有向欧拉图，那么 $G$ 不同的欧拉回路总数 $ec(G)$ 是：
$$
ec(G) = t^{root}(G, k) \prod_{v \in V}(deg(v) - 1) !
$$
其中 $t^{root}(G, k)$ 表示根向树形图的方案数，其中 $k$ 是任意的根。

本质上对于任意的根其欧拉回路的总数都是相同的。

因为是欧拉回路，所以对于一个点的入度和出度是相同的。

无向图是 $\tt NPC$ 问题。

一些细节
  • 图是否联通。
  • 欧拉回路本质上就是若干个环构成，如果说环的顺序不同得到的方案也不同，那么还要乘上 $deg_{rt}$。

具体来说就是考虑每个点第 $i$ 次经过他的时候的贡献是 $deg_u’ - i + 1$，其中 $deg_u’ = deg_u - 1$ 因为每个欧拉回路的最后一条边都可以作为内向生成树的一条边，$deg_u’$ 本质上就是除了内向生成树边以外的所有边。

对于根的情况我们特判因为其没有这样的边，也就是 $deg’_u = deg_u$，所以最后计算贡献的时候少算了一个 $deg_u$ 我们最后乘上即可。

例题

Which Dreamed It

就是板子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;

//#define Fread
#define Getmod

#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
#define getchar gc
#endif // Fread

template <typename T>
void r1(T &x) {
	x = 0;
	char c(getchar());
	int f(1);
	for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
	for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48);
	x *= f;
}

template <typename T,typename... Args> inline void r1(T& t, Args&... args) {
    r1(t);  r1(args...);
}

#ifdef Getmod
const int mod  = 1000003; 
template <int mod>
struct typemod {
    int z;
    typemod(int a = 0) : z(a) {}
    inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}
    inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}
    inline int mul(int a,int b) const {return 1ll * a * b % mod;}
    typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}
    typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}
    typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}
    typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}
    typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}
    typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}
    int operator == (const typemod<mod> &x) const {return x.z == z;}
    int operator != (const typemod<mod> &x) const {return x.z != z;}
};
typedef typemod<mod> Tm;
#endif

//#define int long long
const int maxn = 1e2 + 5;
const int maxm = 2e5 + 5;

Tm fac[maxm];
Tm a[maxn][maxn];
int deg[maxn];
Tm ksm(Tm x,int mi) {
	Tm res(1);
	while(mi) {
		if(mi & 1) res *= x;
		mi >>= 1;
		x *= x;
	}
	return res;
}

void init(int x) {
	fac[0] = 1;
	for(int i = 1; i <= x; ++ i) fac[i] = fac[i - 1] * i;
}
int n;
Tm Guess() {
	Tm res(1), c(mod - 1);
	for(int i = 1; i <= n - 1; ++ i) {
		int pos(i);
		for(int j = i; j <= n - 1; ++ j) 
			if(a[j][i].z > 0) { pos = j; break; }
		if(pos != i) swap(a[pos], a[i]), res *= c;
		Tm inv = ksm(a[i][i], mod - 2);
		res *= a[i][i];
		for(int j = 1; j <= n - 1; ++ j) a[i][j] *= inv;
		for(int j = i + 1; j <= n - 1; ++ j) {
			for(int k = n - 1; k >= i; -- k) {
				a[j][k] -= a[i][k] * a[j][i];
			}
		}
	}
//	puts("Matrix");
//	for(int i = 1; i < n; ++ i) for(int j = 1; j < n; ++ j) printf("%d%c", a[i][j].z, " \n"[j == n - 1] );
//	puts("EndMatrix");
	return res;
}

signed main() {
//    freopen("S.in", "r", stdin);
//    freopen("S.out", "w", stdout);
    int i, j;
    init(2e5);
    while(scanf("%d", &n) != EOF) {
    	if(n == 0) break;
    	for(i = 1; i <= n; ++ i)
    	for(j = 1; j <= n; ++ j) 
    		a[i][j] = 0;
    	for(i = 1; i <= n; ++ i) {
    		int s; r1(s); deg[i] = s;
    		for(j = 1; j <= s; ++ j) {
    			int x; r1(x);
    			if(x != i) a[i][x] -= Tm(1), a[i][i].z ++;
    		}
    	}
    	
    	if(n == 1) { printf("%d\n", fac[deg[1]].z); continue; }
    	
    	Tm ans = Guess();
    	
    	for(i = 1; i <= n; ++ i) if(deg[i] > 0) ans *= fac[deg[i] - 1]; else ans = 0;
    	
    	ans *= deg[1];
    	
    	printf("%d\n", ans.z);
    	
    }
	
	return 0;
}

AGC051D C4

这是一个无向图的欧拉回路计数，这个是 $\tt NPC$ 的，但是我们发现因为其满足欧拉回路的基本性质，也就是意味着如果钦定任意一条边比如 $u \to v$ 的个数，就可以推出所有边的限制。

之后直接进行 $\tt best$ 定理的计算了。

但是这里不同的就是，这里每条边是本质相同的，我们就不能直接使用排列，我们使用组合即可。

对于去除第一条边不能使用的情况，我们直接除以其方案数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;

//#define Fread
#define Getmod

#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
#define getchar gc
#endif // Fread

template <typename T>
void r1(T &x) {
	x = 0;
	char c(getchar());
	int f(1);
	for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
	for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48);
	x *= f;
}

template <typename T,typename... Args> inline void r1(T& t, Args&... args) {
    r1(t);  r1(args...);
}

#ifdef Getmod
const int mod  = 998244353;
template <int mod>
struct typemod {
    int z;
    typemod(int a = 0) : z(a) {}
    inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}
    inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}
    inline int mul(int a,int b) const {return 1ll * a * b % mod;}
    typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}
    typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}
    typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}
    typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}
    typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}
    typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}
    int operator == (const typemod<mod> &x) const {return x.z == z;}
    int operator != (const typemod<mod> &x) const {return x.z != z;}
};
typedef typemod<mod> Tm;
#endif

//#define int long long
const int maxn = 1e6 + 5;
const int maxm = 4;

Tm fac[maxn], inv[maxn], iv[maxn];

Tm ksm(Tm x,int mi) {
	Tm res(1);
	while(mi) {
		if(mi & 1) res *= x;
		mi >>= 1;
		x *= x;
	}
	return res;
}

void init(int x = 1e6) {
	fac[0] = 1;
	for(int i = 1; i <= x; ++ i) fac[i] = fac[i - 1] * i;
	inv[x] = ksm(fac[x], mod - 2);
	for(int i = x - 1; i >= 0; -- i) inv[i] = inv[i + 1] * (i + 1);
	iv[0] = 0;
	for(int i = 1; i <= x; ++ i) iv[i] = inv[i] * fac[i - 1];
}

int a, b, c, d;

Tm C(int a,int b) {
	return a < b ? 0 : fac[a] * inv[b] * inv[a - b];
}

signed main() {
//    freopen("S.in", "r", stdin);
//    freopen("S.out", "w", stdout);
    int i, j;
    init();
    Tm ans(0);
    r1(a, b, c, d);
    if((a & 1) == (b & 1) && (b & 1) == (c & 1) && (c & 1) == (d & 1)) {
    	for(int ia = 0; ia <= a; ++ ia) {
    		int ib = (b - a) / 2 + ia;
    		int ic = (c - b) / 2 + ib;
    		int id = (d - c) / 2 + ic;
    		if(ib < 0 || ic < 0 || id < 0 || ib > b || ic > c || id > d) continue;
//    		printf("%d %d %d %d\n", ia, ib, ic, id);
    		int A1 = 1ll * (ia + b - ib) * (ib + c - ic) % mod * (ic + d - id) % mod;
    		int C1 = 1ll * (ia + b - ib) * (ic) % mod * (ic - c) % mod;
    		int B1 = 1ll * (ib) * (ib - b) % mod * (ic + d - id) % mod;
    		Tm Del = ((A1 + B1 + C1) % mod + mod) % mod;
//    		printf("Del = %d\n", Del.z);
    	
    		Tm T1 = iv[ia + b - ib] * iv[ib + c - ic] * iv[ic + d - id];
    		Tm T2 = C(ia + b - ib, ia) * C(ib + c - ic, ib) * C(ic + d - id, ic) * C(id + a - ia, id);
    		ans += T1 * T2 * Del;
    	}
    }
    printf("%d\n", ans.z);
	return 0;
}