acwing算法提高之图论--欧拉回路和欧拉路径

1 介绍

本专题用来记录欧拉回路和欧拉路径相关的题目。

相关结论：
（1）对于无向图，所有边都是连通的。
（1.1）存在欧拉路径的充要条件：度数为奇数的结点只能是0个或者2个。
（1.2）存在欧拉回路的充要条件：度数为奇数的结点只能是0个。

（2）对于有向图，所有边都是连通的。
（2.1）存在欧拉路径的充要条件1：所有结点的出度均等于其入度。
（2.1）存在欧拉路径的充要条件2：除去两个结点外，其余所有结点的出度等于入度。且除去的那两个结点，其中一个结点的出度比入度多1（起点），另一个结点的入度比出度多1（终点）。
（2.2）存在欧拉回路的充要条件：所有结点的出度均等于其入度。

2 训练

题目1：1123铲雪车

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    double x1, y1, x2, y2;
    cin >> x1 >> y1;
    
    double sum = 0;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        sum += sqrt(dx * dx + dy * dy) * 2;
    }
    
    int minutes = round(sum / 1000 / 20 * 60);
    int hours = minutes / 60;
    minutes %= 60;
    
    printf("%d:%02d\n", hours, minutes);
    
    return 0;
}

题目2：1184欧拉回路

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 400010;

int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];

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

void dfs(int u) {
    for (int &i = h[u]; ~i;) {
        if (used[i]) {
            i = ne[i];
            continue;
        }
        
        used[i] = true;
        if (type == 1) used[i ^ 1] = true;
        
        int t;
        
        if (type == 1) {
            t = i / 2 + 1;
            if (i & 1) t = -t;
        } else {
            t = i + 1;
        }
        
        int j = e[i];
        i = ne[i];
        dfs(j);
        
        ans[++cnt] = t;
    }
}

int main() {
    scanf("%d", &type);
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        if (type == 1) add(b, a);
        din[b]++, dout[a]++;
    }
    
    if (type == 1) {
        for (int i = 1; i <= n; ++i) {
            if (din[i] + dout[i] & 1) {
                puts("NO");
                return 0;
            }
        }
    } else {
        for (int i = 1; i <= n; ++i) {
            if (din[i] != dout[i]) {
                puts("NO");
                return 0;
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        if (h[i] != -1) {
            dfs(i);
            break;
        }
    }
    
    if (cnt < m) {
        puts("NO");
        return 0;
    }
    
    puts("YES");
    for (int i = cnt; i; --i) printf("%d ", ans[i]);
    puts("");
    
    return 0;
}

题目3：1124骑马修栅栏

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n = 500, m;
int g[N][N];
int ans[1100], cnt;
int d[N];

void dfs(int u) {
    for (int i = 1; i <= n; ++i) {
        if (g[u][i]) {
            g[u][i]--, g[i][u]--;
            dfs(i);
        }
    }
    ans[++cnt] = u;
}

int main() {
    cin >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b]++, g[b][a]++;
        d[a]++, d[b]++;
    }
    
    int start = 1;
    while (!d[start]) start++;
    for (int i = 1; i <= n; ++i) {
        if (d[i] % 2) {
            start = i;
            break;
        }
    }
    
    dfs(start);
    
    for (int i = cnt; i; i--) printf("%d\n", ans[i]);
    
    return 0;
}

题目4：1185单词游戏

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
int din[N], dout[N], p[N];
bool st[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    char str[1010];
    
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        memset(st, 0, sizeof st);
        for (int i = 0; i < 26; ++i) p[i] = i;
        
        for (int i = 0; i < n; ++i) {
            scanf("%s", str);
            int len = strlen(str);
            int a = str[0] - 'a', b = str[len - 1] - 'a';
            st[a] = st[b] = true;
            dout[a]++, din[b]++;
            p[find(a)] = find(b);
        }
        
        int start = 0, end = 0;
        bool success = true;
        for (int i = 0; i < 26; ++i) {
            if (din[i] != dout[i]) {
                if (din[i] == dout[i] + 1) end++;
                else if (din[i] + 1 == dout[i]) start++;
                else {
                    success = false;
                    break;
                }
            }
        }
        
        if (success && !(!start && !end || start == 1 && end == 1)) success = false;
        
        int rep = -1;
        for (int i = 0; i < 26; ++i) {
            if (st[i]) {
                if (rep == -1) rep = find(i);
                else if (rep != find(i)) {
                    success = false;
                    break;
                }
            }
        }
        
        if (success) puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }
    
    return 0;
}