博客

在一个图中，存在这样一条路径，它经过每条边恰好一次，并在最后一个顶点时会到第一个顶点，这样的路径叫做欧拉回路。

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 200;

struct stack
{
    int top, node[maxn];
} s;
int e[maxn][maxn], vertex;

void dfs(int x)
{
    s.node[++s.top] = x;
    for (int i = 0; i < vertex; i++) {
        if (e[i][x] > 0) {
            e[i][x] = e[x][i] = 0;  //删除这条边
            dfs(i);
            break;
        }
    }
}

void fleury(int x)
{
    int flag;
    s.top = 0;
    s.node[s.top] = x;
    while (s.top >= 0) {
        flag = 0;
        for (int i = 0; i < vertex; i++) {
            if (e[s.node[s.top]][i] > 0) {
                flag = 1;
                break;
            }
        }
        if (!flag)
            printf("%d ", s.node[s.top--] + 1);
        else
            dfs(s.node[s.top--]);
    }
    puts("");
}

int main( )
{
    int x, y, edge, degree, num = 0, start = 0;
    scanf("%d%d", &vertex, &edge);
    memset(e, 0, sizeof(e));
    for (int i = 0; i < edge; i++) {
        scanf("%d%d", &x, &y);
        e[x - 1][y - 1] = e[y - 1][x - 1] = 1;
    }
    for (int i = 0; i < vertex; i++) {
        degree = 0;
        for (int j = 0; j < vertex; j++)
            degree += e[i][j];
        if (degree & 1) {
            start = i;
            num++;
        }
    }
    if (num == 0 || num == 2)
        fleury(start);
    else
        printf("No Euler path\n");
    return 0;
}

/*
12 21
1 3
1 4
2 3
3 4
4 5
2 8
3 9
4 10
8 9
9 10
10 11
9 12
10 12
6 3
6 9
3 7
9 7
7 4
7 10
4 11
10 5
*/

参考博客：https://blog.csdn.net/u011466175/article/details/18861415