Euler 回路

不难发现,在欧拉回路中,进和出应该是对应的,也就是说,除了起点和终点外,其他点的进出次数应该相等

无向图
奇点,一个点的deg(u)\textbf{deg}(u) (即度数)为奇数

  1. 如果一个无向图是连通的,且最多只有22 个奇点,一定存在欧拉回路
  2. 如果有22 个奇点,必须是一个奇点为起点,另一个为终点
  3. 如果奇点不存在,从任意点uu 出发,一定会回到uu,称为欧拉回路

有向图
当然前提是有向图必须是连通的

  1. 最多只能有两个点的入度不等于出度,并且起点的outdeg(u)=indeg(u)+1\text{outdeg}(u) = \text{indeg}(u) + 1
    终点indeg(u)=outdeg(u)+1\text{indeg}(u) = \text{outdeg}(u) + 1

代码模版,用vis(u,v)\text{vis}(u, v) 标记边是否被访问过

1
2
3
4
5
6
7
8
stack<PII> stk;
void euler(int u) {
for (int v = 0; v < n; v++) if (G[u][v] && !vis[u][v]) {
vis[u][v] = vis[v][u] = 1;
euler(v);
stk.push(PII(u, v));
}
}

Play On Words
大意是给你一些单词,判断是否存在一种排列,使得每个单词的第一个字母和上一个单词的最后一个字母相同

  • 不难想到先用并查集,将每个单词的第一个字母uu 和最后一个字母vv 抽出来,则每个单词对应
    (u,v)(u, v) 这个有向边,可以先使用并查集判连通
    初始化连通块数量cc=ncc = n,执行并查集合并的时候,cc=1cc-=1,只有cc=1cc = 1 的时候才是合法情况
  • 那么问题抽象称为,是否存在一种方案,使得每个单词恰好只使用11
    也就是对应欧拉路径中,每条边恰好只经过一次,那么当且仅当存在欧拉路径的时候,问题有解
  • 有向图的欧拉路径,入度deg(u)++\text{deg}(u)++,出度deg(u)\text{deg}(u)--
    这样欧拉回路的判定条件简化为,最多只有两个点deg(u)0\text{deg}(u) \neq 0
    并且其中一个点deg(u)=1\text{deg}(u) = -1 作为起点,另一个点deg(u)=1\text{deg}(u) = 1 作为终点
    对于有向边(u,v)(u, v)deg(v)++,deg(u)\text{deg}(v)++, \text{deg}(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
const int maxn = 1e5 + 10;
char str[maxn];
int n, cc = 26;
int deg[27], pa[27], vis[27];

inline int get(int x) {
return pa[x] == x ? x : pa[x] = get(pa[x]);
}

void init() {
cc = 26;
memset(vis, 0, sizeof vis);
memset(deg, 0, sizeof deg);

for (int i = 0; i < 26; i++) pa[i] = i;
}

void solve() {
vector<int> res;

for (int i = 0; i < 26; i++) {
if (deg[i] != 0) res.push_back(deg[i]);
}
sort(res.begin(), res.end());
//debug(res[0]);

if (res.empty()) {
puts("Ordering is possible.");
return;
}

if (res.size() == 2 && res[0] == -1 && res[1] == 1) {
puts("Ordering is possible.");
return;
}

puts("The door cannot be opened.");
return;
}


int main() {
freopen("input.txt", "r", stdin);
int cas;
cin >> cas;

while (cas--) {
// init
init();

scanf("%d", &n);

for (int i = 0; i < n; i++) {
scanf("%s", str);

int u = str[0] - 'a', v = str[strlen(str)-1] - 'a';
vis[u] = vis[v] = 1;
deg[v]++, deg[u]--;

u = get(u), v = get(v);
if (u != v) {
pa[u] = v;
cc--;
}
}

// then solve
for (int i = 0; i < 26; i++) if (!vis[i]) cc--;

if (cc != 1) {
puts("The door cannot be opened.");
continue;
}

// euler path
solve();
}
}

Euler 回路有关的构造

Min Cost String
题意大致是构造字符串,使得代价最小
定义代价为,1i<jn1 \leqslant i < j \leqslant n,满足S[i]=S[j] and S[i+1]=S[j+1]S[i] = S[j] \ \textbf{and} \ S[i+1] = S[j+1]
需要构造的字符串长度为nn,一共可以使用k[1,26]k \in [1, 26] 个不同的小写字母

  1. 首先很容易想到,如果nn 很小,而kk 很大(k=26)(k=26) 的情况,只需要依次使用不同的字母cc 构造即可
  2. 可以发现随着nn 增加,一定会产生重复代价,假设我们构造了S[i]=u,S[i+1]=vS[i] = u, S[i+1] = v
    那么存在一个位置jj 满足S[j]=u,S[j+1]=vS[j] = u, S[j+1] = v,需要让这个重复代价尽可能小
  3. 也就是说,一开始需要构造尽可能不同的二元组(u,v)(u, v),并且保证(u,v)(u, v) 只出现一次
    如果在S[i]S[i] 处出现(u,v)(u, v),在S[j]S[j] 中也出现(u,v)(u, v),那么有Si=Sj,Si+1=Sj+1S_i = S_j, S_{i+1} = S_{j+1}
    会产生额外代价
    一开始的时候尽量满足(u,v)(u, v) 只用一次,实际上就是找一条欧拉路径
    而尽量不同的二元组(u,v)(u, v),可以在kk 个点的完全图上遍历
  4. kk 个点的完全图有k2k^2 条边,每条边(i,j)(i, j) 都出现22 次,所以完全图没有奇点
    注意,这里无向图转为有向图,(u,v)(u, v) 无向边看成是uvu \to vvuv \to u,这样构造就没有奇点
    没有奇点的图一定存在欧拉路径,并且从任意一点开始dfs\text{dfs},一定会回到这个点 (也就是开始重复)
    所以在k2<n1k^2 < n-1 的情况下,一定会产生重复代价
    假设构造出Si=uS_i = u,那么欧拉路径第mm 次到达uu 时,满足
    Si=Si+n=Si+2n=Si+(m1)n=u\displaystyle S_i = S_{i+n} = S_{i+2n} = \cdots S_{i+(m-1)n} = u
    对于边(u,v)(u, v),只在欧拉路径回到uu 这个点时产生代价,每一次走欧拉回路时,(u,v)(u, v) 只出现一次
    所以这个代价最小
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
const int maxn = 27;
int n, k;
int G[maxn][maxn], vis[maxn][maxn];
vector<int> path;

void build() {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++)
G[i][j] = 1;
}
}

void dfs(int u) {
for (int v = 0; v < k; v++) {
if (G[u][v] && vis[u][v] == 0) {
vis[u][v] = 1;
dfs(v);
path.push_back(v);
}
}
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> k;

// build
memset(vis, 0, sizeof vis);
build();

dfs(0);
string res = "";
for (int i = 0; i < n; i++) {
int id = i % path.size();
res += string(1, (char)('a' + path[id]));
}
cout << res << endl;
}

拓扑排序和 DAG

DAG 相关的问题,很容易让人想到拓扑排序

构造有向无环图

  1. 如果仅考虑有向边构成的有向连通块G(V,E)G'(V', E'),那么问题很容易解决
    只需要对GG' 进行拓扑排序,队列中元素个数恰好等于VV',那么存在拓扑序
    否则不存在拓扑序
  2. 考虑整个图GG,如果仅加入有向边EE',那么有向连通块GG' 之外的离散点uu
    其入度满足deg(u)=0\text{deg}(u) = 0,这些点仍然可以进拓扑队列,存在拓扑序
  3. 实际上将有向连通块GG' 缩点成UU,实际上UUGG'dfs\text{dfs} 树的根
    对于UU 之外的离散点uiu_i,由于他们的deg(ui)=0\text{deg}(u_i) = 0
    这些点一开始就会进入拓扑队列中,必然能够构造出 DAG 如下
    G={u0u1Uuk}G = \{u_0 \to u_1 \to \cdots \to U \to \cdots u_k \}
    如果UU 是一个 DAG,那么GG 也是一个 DAG
  4. 具体来说,一开始只加入有向边,对于有向边之外的离散点,初始化deg(u)=0\text{deg}(u) = 0
    然后将所有deg(u)=0\text{deg}(u) = 0 的点放入拓扑队列中,并执行拓扑排序
    类似tarjan\text{tarjan} 算法,拓扑序即拓扑队列中出队顺序
    定义一个dfn(u)\text{dfn}(u) 记录节点uu 出队列的时间戳
  5. 对于未指定方向的边(x,y)(x, y),拓扑排序后,只需要从dfn\text{dfn} 小的点指向大的点
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
const int maxn = 2e5 + 10, maxm = 2e5 + 10;
int n, m;

int head[maxn], ver[maxm], ne[maxm], idx = 1, deg[maxn], dfn[maxn], num = 0;

class Edge {
public:
int a, b;
Edge(int a = 0, int b = 0) : a(a), b(b) {}
};

vector<Edge> edges, e;

void add(int a, int b) {
ver[++idx] = b, ne[idx] = head[a], head[a] = idx;
}

bool topo() {
queue<int> que;
for (int u = 1; u <= n; u++) if (deg[u] == 0) que.push(u);

while (que.size()) {
auto x = que.front(); que.pop();
dfn[x] = ++num;

for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (--deg[y] == 0) que.push(y);
}
}

return num == n;
}

void solve() {
for (auto x : e) {
printf("%d %d\n", x.a, x.b);
}
for (auto x : edges) {
int u = x.a, v = x.b;
if (dfn[u] > dfn[v]) swap(u, v);
printf("%d %d\n", u, v);
}
}

void init() {
memset(head, 0, (n+1) * 4);
memset(deg, 0, (n+1) * 4);
memset(dfn, 0, (n+1) * 4);
idx = 1, num = 0;
edges.clear(), e.clear();
}

int main() {
freopen("input.txt", "r", stdin);
int cas;
cin >> cas;

while (cas--) {
scanf("%d%d", &n, &m);
init();

while (m--) {
int t, a, b;
scanf("%d%d%d", &t, &a, &b);

if (t) {
add(a, b);
deg[b]++;
e.push_back(Edge(a, b));
}
else edges.push_back(Edge(a, b));
}

if (!topo()) {
puts("NO");
continue;
}
puts("YES");
solve();
}
}