解答：

本题提到了EL路径，即欧拉路径。EL正是大名鼎鼎的欧拉(Euler)的缩写。

欧拉路径(Euler path)：如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。

欧拉路径问题简称“一笔画”问题，这个问题我们小学二年级就应该学过，我还记得当时有个著名的七桥问题。

题目中给的是无向图，那么如何判断一个无向图能不能一笔画呢？有下面定理：

无向图存在欧拉路径的充要条件：度为奇数的点的数量为0个或2个。

当然，你完全可以不知道这些，因为题目条件已经毫无保留的告诉你了：“当G中度为奇数的顶点个数为不大于2的偶数时”。不就是无向图存在欧拉路径的充要条件吗？

⑴ 这样思路就有了：

• 第一步：统计所有点的度。
• 第二步：统计所有点中度为奇数的点的个数。
• 第三步：检查度为奇数的点个数是否为0或者2。

这道题称为408史上最简单算法题毫不过分，只因为第一次考图就离谱的送分，一送还送15分，但我估计要送就送这么一次，以后的考生就没这么好运了。

同学们可以用下面几张图玩一下一笔画。

⑵ 根据上述思路，C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>
#define MAXV 11

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
}MGraph;

int IsExistEL(MGraph G) {
    int degrees[G.numVertices];
    memset(degrees, 0, sizeof(degrees));
    // 遍历无向图统计所有点的度
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            degrees[i] += G.Edge[i][j];
        }
    }
    int count = 0;
    // 遍历degrees数组统计度为奇数的点的个数
    for (int i = 0; i < G.numVertices; i++) {
        if (degrees[i] % 2 != 0) {
            count++;
        }
    }
    // 检查度为奇数的点个数是否为0或者2
    if (count == 0 || count == 2) {
        return 1;  // 存在EL路径
    } else {
        return 0;  // 不存在EL路径
    }
}

int main() {
    // 以图(a)为例
    MGraph G;
    G.numEdges = 6;
    G.numVertices = 5;
    memset(G.VerticesList, 0, sizeof(G.numVertices));
    char V[5] = {'a', 'b', 'c', 'd', 'e'};
    for (int i = 0; i < G.numVertices; i++) {
        G.VerticesList[i] = V[i];
    }
    memset(G.Edge, 0, sizeof(G.numVertices));
    int M[5][5] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 1, 0}, {0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}};
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            G.Edge[i][j] = M[i][j];
        }
    }
    if (IsExistEL(G)) {
        printf("There is a Euler path. ");
    } else {
        printf("There is no Euler path. ");
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
• 空间复杂度： O(n) ，开辟了 O(n) 大小的辅助数组。

如果到这里就结束了，这道题也太简单了吧，明显需要进行优化。时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>
#define MAXV 11

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
}MGraph;

int IsExistEL(MGraph G) {
    int degree = 0;
    int count = 0;
    // 遍历无向图统计所有点的度
    for (int i = 0; i < G.numVertices; i++) {
        degree = 0; // 重置
        // 计算点i的度
        for (int j = 0; j < G.numVertices; j++) {
            degree += G.Edge[i][j];
        }
        // 检查点i的度是否为奇数
        if (degree % 2 != 0) {
            count++;
        }
    }
    // 检查度为奇数的点个数是否为0或者2
    if (count == 0 || count == 2) {
        return 1;  // 存在EL路径
    } else {
        return 0;  // 不存在EL路径
    }
}

int main() {
    // 以图(a)为例
    MGraph G;
    G.numEdges = 6;
    G.numVertices = 5;
    memset(G.VerticesList, 0, sizeof(G.numVertices));
    char V[5] = {'a', 'b', 'c', 'd', 'e'};
    for (int i = 0; i < G.numVertices; i++) {
        G.VerticesList[i] = V[i];
    }
    memset(G.Edge, 0, sizeof(G.numVertices));
    int M[5][5] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 1, 0}, {0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}};
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            G.Edge[i][j] = M[i][j];
        }
    }
    if (IsExistEL(G)) {
        printf("There is a Euler path. ");
    } else {
        printf("There is no Euler path. ");
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
• 空间复杂度： O(1) ，使用了常数个临时变量。