1. 无向图欧拉路径

P2731 [USACO3.3]骑马修栅栏 Riding the Fences

之所以要用邻接矩阵是因为一条边只能走一次，走过一条边这条边的另一个方向也不能走了，邻接矩阵便于删除走过的边的另一个方向。

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
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 5e2;
const int MAXm = 1024;

template <typename T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}
template <typename T, typename ...Argv>
inline void read(T &n, Argv &...argv) {
    read(n), read(argv...);
}

int n, m, source = 1, edge[MAXn + 10][MAXn + 10], deg[MAXn + 10];
int top, stk[MAXm * 2 + 10];
void Dfs(int cur) {
    for (int i = 1; i <= n; ++i) {
        if (edge[cur][i]) {
            --edge[cur][i]; --edge[i][cur];
            Dfs(i);
        }
    }
    stk[++top] = cur;
}

signed main() {
    read(m);
    for (int i = 1, u, v; i <= m; ++i) {
        read(u, v);
        ++edge[u][v]; ++edge[v][u];
        ++deg[u]; ++deg[v];
        n = max(n, max(u, v));
    }
    for (int i = 1; i <= n; ++i) {
        if (deg[i] & 1) {
            source = i;
            break;
        }
    }
    Dfs(source);
    for (int i = top; i; --i) {
        printf("%d\n", stk[i]);
    }
}

空间开不下 O(n2)O(n^2) 怎么办，听别人说要用什么当前弧优化，留坑待补……

2. 有向图欧拉路径

P7771 【模板】欧拉路径

有向图求欧拉路径，因为边没有另一个方向，所以不用删另一个方向。直接用邻接表即可。

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
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 1e5;
const int MAXm = 2e5;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : c ^ '0';for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &n, Argv &...argv) {
    read(n), read(argv...);
}

inline bool cmp(int a, int b) {
    return a > b;
}

vector<int> edge[MAXn + 10];
int top, stk[MAXm + 10];
void Dfs(int cur) {
    while (!edge[cur].empty()) {
        int to = edge[cur].back();
        edge[cur].pop_back();
        Dfs(to);
    }
    stk[++top] = cur;
} 

int n, m;
int indeg[MAXn + 10], outdeg[MAXn + 10];
signed main() {
    read(n, m);
    for (int i = 1, u, v; i <= m; ++i) {
        read(u, v);
        edge[u].push_back(v);
        ++outdeg[u]; ++indeg[v];
    }
    int cnt1 = 0, cnt2 = 0, bg = 0;
    for (int i = 1; i <= n; ++i) {
        if (indeg[i] == outdeg[i] + 1) {
            ++cnt1;
        } else if (indeg[i] == outdeg[i] - 1) {
            ++cnt2;
            bg = i;
        } else if (indeg[i] != outdeg[i]) {
            puts("No");
            return 0;
        }
    }
    if (!((cnt1 == 1 && cnt2 == 1) || (cnt1 == 0 && cnt2 == 0))) {
        puts("No");
        return 0;
    }
    if (bg == 0) {
        bg = 1;
    }
    for (int i = 1; i <= n; ++i) {
        sort(begin(edge[i]), end(edge[i]), cmp);
    }
    Dfs(bg);
    for (int i = top; i; --i) {
        printf("%d ", stk[i]);
    }
    puts("");
    return 0;
}