构造题中的欧拉回路

First Post:

Last Update:

欧拉回路在构造题中的一些应用.

从欧拉回路开始#

(有向图/无向图的)欧拉路径是一条回路, 满足其恰经过所有边一次. (有向图/无向图的)欧拉回路是起点和终点相同的一条欧拉路径. (有向图/无向图的)欧拉通路是起点和终点不同的一条欧拉路径.

有向图存在欧拉回路: 将边看成无向边后图联通, 且所有点入度均等于出度.
有向图存在欧拉通路: 将边看成无向边后图联通, 且除两个点外, 所有点入度均等于出度; 那两个点中, 其中一个出度比入度大 1, 作为欧拉通路的起点; 另一个入度比出度大 1, 作为欧拉通路的终点.
无向图存在欧拉回路: 所有点度数均为偶数.
无向图存在欧拉通路: 除两个点度数为奇数外, 所有点度数均为偶数. 那两个点中, 一个作为欧拉通路之起点, 另一个作为终点.

构造欧拉回路可以直接 dfs. 具体来说, 我们不断找环, 用栈合并即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs_directed(int u){
  for(int &e=head[u]; e; e=Next[e]) {
    if(vis[e]) continue; int t=e;
    vis[e]=1; dfs_directed(ver[e]);
    stk[++top]=t;
  }
}
void dfs_undirected(int u) {
  for(int &e=head[u]; e; e=Next[e]) {
    if(vis[e>>1]) continue; int t=e;
    vis[e>>1]=1; dfs_undirected(ver[e]);
    stk[++top] = (t&1) ? -(t>>1) : (t>>1);
  }
}

题目#

直接涉及欧拉回路性质的问题#

AGC#032C#

给定一联通图 , 问边集能否被划分为三个不相交的回路.

显然, 由回路之性质, 解存在的必要条件是每个点的度数均为偶数, 也即图存在欧拉回路. 考察图上点度数之最大值:

  • 若图上点度数最大值为 , 显然无解.
  • 若图上点度数最大值为 , 考察这样的点的个数:
    • 若这样的点的个数为 , 显然无解.
    • 若这样的点的个数为 , 则有解当且仅当删去一个这样的点后图上仍存在环.
    • 若这样的点的个数为 或更多, 则必然有解.
  • 若图上点度数最大值为 或更多, 则显然有解.
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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 2000005
int n, m; int d[_], vis[_], used[_], head[_], ver[_], Next[_], tot, lop;
void add(int u, int v) {
  ver[++tot]=v, Next[tot]=head[u], head[u]=tot;
}
void dfs(int u, int t) {
  // cerr << u << endl;
  for(int e=head[u]; e; e=Next[e]) {
    int v=ver[e]; if(vis[v]) { ++vis[v]; continue; }
    else if(v==t) {  ++vis[v]; continue; }
    else { ++vis[v]; dfs(v, t); }
  }
}
int main() {
  tot=1; rd(n); rd(m); f(i,1,m) {
    int u=rd(), v=rd();
    add(u, v); add(v, u);
    ++d[u]; ++d[v];
  }
  // f(i,1,n) cerr << d[i] << endl;
  f(i,1,n) if(d[i]&1) { puts("No"); exit(0); }
  int dmax = 2, dcount = 0;
  f(i,1,n) {
    if(d[i]>dmax) { dmax=d[i], dcount=1; }
    else if(d[i]==dmax) ++dcount;
  }
  cerr << dmax << ' ' << dcount << endl;
  if(dmax <= 2) { puts("No"); exit(0); }
  else if(dmax >= 6) { puts("Yes"); exit(0); }
  else {
    if(dcount <= 1) { puts("No"); exit(0); }
    else if(dcount >= 3) { puts("Yes"); exit(0); }
    else {
      int node[2], cnt=-1; f(i,1,n) if(d[i]==dmax) node[++cnt]=i;
      vis[node[0]]=1; dfs(node[0], node[1]); puts((vis[node[1]] == 2) ? "Yes" : "No"); exit(0);
    }
  }
  return 0;
}

与环的性质有关的简单构造#

CF#547 D#

给定平面上 个点 . 你需要给每个点染成红或蓝色, 使得每条线上的红点与蓝点的个数之差为 , 或 .

我们首先将点的染色对应为赋值为 或 . 那么限制对应为每行每列的和为 , 或 .

我们将行列均建成点, 称第 行对应的点为 , 第 列对应的点是 . 将平面上的点 对应为双向边 . 考察若原图有一欧拉回路, 则可使每行每列均为 . 具体来说, 考察每条边是被正向还是被反向经过来定对应的点的权值为 或 , 由于欧拉回路是环套环结构所以每个新图中的点的出入次数相同, 也即和为 . 考虑给图加上一些边使得加完边后的图有欧拉回路, 如果没有两条边被加在同一个点上那么去掉这些新加的边的贡献后必然有每个点被出入的次数差的绝对值在 以内. 也即合法. 我们考虑所有入度和出度奇偶性不相等的点, 在它们间每对加边即可.

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 1000005
#define N 200005
int head[_], ver[_], Next[_], vis[_], tot, stk[_], d[_], ind[_], outd[_], ans[_], top;
void add(int u, int v) {
  // cerr << "add " << u << ' ' << v << endl;
  ver[++tot]=v, Next[tot]=head[u], head[u]=tot;
}
void dfs_undirected(int u) {
  for(int &e=head[u]; e; e=Next[e]) {
    if(vis[e>>1]) continue; int t=e;
    vis[e>>1]=1; dfs_undirected(ver[e]);
    ans[t>>1] = t&1 ? 0 : 1;
  }
}
int x[_], y[_], n;
int main() {
  tot=1; rd(n); f(i,1,n) { rd(x[i]); rd(y[i]); add(x[i], y[i]+N); add(y[i]+N, x[i]); ++d[x[i]]; ++d[y[i]+N]; }
  int j=0;
  f(i,1,2*N) if(d[i]&1) j?add(j, i), add(i, j), j=0:j=i;
  f(i,1,2*N) dfs_undirected(i);
  f(i,1,n) cout << (ans[i]?'b':'r');
  return 0;
}

CF#528C#

有 个点之间通过 条无向边连接, 保证任意两点间联通. 你可以加入若干条无向边, 那之后给每条无向边定向, 使得每个点的入度和出度均为偶数. 你需要使加入的边的数量最少.

若定向后每个点的出度与入度均为偶数, 容易发现原图上每个点的度数也均为偶数, 也即原图存在欧拉路. 又所有点的入度和也为偶数, 故原图存在总边数为偶数的欧拉路. 不断寻找度数为奇数的点并两两连边, 然后依据总边数决定是否加入一个自环即可.

接下来对于一个总长度为偶数的欧拉路, 我们总能构造出一个给边定向的方案使得每个点之入度与出度均为偶数. 我们考虑对于欧拉回路上每条边, 若其为欧拉回路上第奇数条边, 定向为其被经过的方向, 否则定向为其被经过的方向之反向. 由于该欧拉路的总场为偶数, 这是容易被证明的, 留给读者做习题.

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 1000005
#define N 200005
int head[_], ver[_], Next[_], vis[_], tot, stk[_], d[_], ind[_], outd[_], top;
pir ans[_];
void add(int u, int v) {
  // cerr << "add " << u << ' ' << v << endl;
  ver[++tot]=v, Next[tot]=head[u], head[u]=tot;
}
void dfs_undirected(int u) {
  for(int &e=head[u]; e; e=Next[e]) {
    if(vis[e>>1]) continue; int t=e;
    vis[e>>1]=1; dfs_undirected(ver[e]);
    ++top; ans[top]=top&1 ? make_pair(u, ver[t]) : make_pair(ver[t], u);
  }
}
int n, m;
int main() {
  tot=1; rd(n); rd(m); f(i,1,m) {
    int u=rd(), v=rd(); ++d[u]; ++d[v]; add(u, v); add(v, u);
  }
  int j=0;
  f(i,1,n) if(d[i]&1) j?add(i, j), add(j, i), j=0, ++m:j=i;
  if(m&1) add(1, 1), add(1, 1), ++m;
  cout << m << endl;
  dfs_undirected(1);
  f(i,1,top) cout << ans[i].fir << ' ' << ans[i].sec << endl;
  return 0;
}

与汉密顿路的联系#

IOI2016 railroad#

题面略.

把速度当成点, 特殊路段当成边建出图. 容易发现如果直接在可以转移的过山车间连边, 边数是过多的. 我们改为构造一种特殊的边(代价为 ), 可以加速, 那之后将速度小于等于 变为速度恰为 . 然后我们连一条从最大值到最小值的边, 这样就是一个环状结构了. 我们可以暴力把边连出来, 然后变成了最小汉密顿路问题, NPC, 寄了.

我们换个想法: 汉密顿路是 NPC, 但是欧拉回路有很多好的性质. 我们考虑原问题, 如果把路径当做是一种方案, 我们发现这其实是一个有向图加边变成欧拉图的问题. 这是很经典且可做的问题.

我们先不考虑图的连通性问题, 那么考虑所有入度不等于出度的点, 直接连边即可.

然后我们要使图联通, 必然是加若干双向边. 假设把每个有 Euler 回路的有向图缩成一个点, 直接 MST 把所有点合并成一棵树即可.

与环的性质有关的复杂构造#

AGC#017E#

给定 块拼图, 每块拼图形如如下形状, 其中三部分的宽度均为 :

具体来说, 左侧矩形高度为 , 距离中间矩形底部 ; 右侧矩形高度为 , 距离中间矩形底部 . 中间矩形的高度为 .

判定是否可以将所有拼图放进一个平面内, 使得:

  • 所有拼图中间部分的下底面均与平面的 轴对齐.
  • 对于非中间部分的下底面, 要么和平面的 轴对齐, 要么和另一块拼图的非中间部分的上顶面对齐.
  • 拼图只能平移.

容易发现拼图必然是若干个顺次排列的连通块, 每个联通块的两个中间矩形之间必然相隔 .

考虑建图. 我们将拼图的左侧矩形抽象为一个点, 将右侧矩形抽象为一个点, 然后在这两个点之间连边. 如果一个左侧矩形接地, 我们将其抽象为点 , 否则我们将其抽象为 . 如果一个右侧矩形接地, 我们将其抽象为 , 否则我们将其抽象为 . 那么一个连通块被我们抽象为一条路径. 问题转化为选若干不相交路径覆盖所有边, 要求起点是某个 而终点是某个 .

我们新建节点 , 如果答案中有从 到 的路径, 那么我们从 向 连边, 从 向 连边. 容易发现这样连边后图是 Euler 图. 由 Euler 图的性质我们可以知道 向每个点的连边数量, 而这是与答案无关的. 于是我们把这些边补上, 如果图有欧拉回路, 那么就有解.

但是这是错的, 可能存在这样的情况: 构成的回路, 明显这是不合法的. 也即我们将边补上后, 原图的弱联通分量只有包含 的那一个.

AGC#018F#

给定两棵标号相同的树, 你要给每个标号分配一个权值, 使得分配后每个节点的子树内的权值和为 或 . 构造一种方案, 或者说明不存在这样的方案.

这是我接触欧拉回路在构造题中运用的第一道题, 现在我以这道题为本文收尾.

首先考虑有解的必要条件. 容易发现 , 所以我们可以求出某个标号被分配到的权值的奇偶性: 若一个节点有奇数个儿子, 则本身是偶数, 否则本身是奇数. 如果两棵树上某个标号被分配的权值不同, 那么肯定无解. 否则如果两个标号都为奇数, 我们在对应的树之间的对应节点间连边. 这样除了根节点, 其他节点的度数均为偶数. 我们再在两个根之间连一条边. 由于所有节点的度数均为偶数, 我们可以跑欧拉回路. 对于树间的一条边, 如果其从其二棵树指向第一棵树, 那么这个标号赋值 1, 否则赋值 -1. 其他的节点赋值 0. 我们来证明这个结论的正确性: 考虑一个节点所在的子树, 由于是一条回路, 所以其被进出次数是一样的. 考虑到这个节点可能有父节点, 这条边不会造成权值贡献. 所以这个节点被进出次数差是 或 , 也即这个节点的子树和是 或 .

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 1000000
int n, R1, R2; int head[_], Next[_], ver[_], vis[_], ans[_], deg[_], tot, E0;
void add(int u, int v) {
  ver[++tot]=v, Next[tot]=head[u], head[u]=tot;
  // cerr << "add " << u << ' ' << v << endl;
}
void dfs(int u) {
  for(int &e=head[u]; e; e=Next[e]) {
    int v=ver[e]; if(vis[e>>1]) continue;
    vis[e>>1]=1; if(e>E0) ans[ (ver[e] > n ? ver[e]-n : ver[e]) ] = e&1 ? 1 : -1; dfs(v);
  }
}
int main() {
  tot=1; rd(n); f(i,1,n) {
    int u=rd(); if(u==-1) { R1=i; continue; }
    add(u, i); add(i, u);
    ++deg[u];
  } f(i,1,n) {
    int u=rd(); if(u==-1) { R2=i; continue; }
    add(u+n, i+n); add(i+n, u+n);
    ++deg[u+n];
  }
  add(R1, R2+n); add(R2+n, R1);
  E0=tot;
  f(i,1,n) {
    deg[i]&=1; deg[i+n]&=1;
    if(deg[i]!=deg[i+n]) { puts("IMPOSSIBLE"); return 0; }
    else if(!deg[i]) { add(i, i+n); add(i+n, i); }
  }
  dfs(R1);
  puts("POSSIBLE");
  f(i,1,n) cout << ans[i] << " \n"[i==n];
  return 0;
}