c语言用关联矩阵判断是否欧拉图

判断一个图是否为欧拉图，可以使用关联矩阵。关联矩阵是一个 $n \times m$ 的矩阵，其中 $n$ 表示图的节点数，$m$ 表示图的边数。矩阵中的每一个元素 $a_{ij}$ 表示第 $i$ 个节点和第 $j$ 条边是否相连，如果是，则为 $1$，否则为 $0$。

对于无向图，如果该图是欧拉图，则必须满足以下两个条件：

1. 图是连通的
2. 所有节点的度数均为偶数

对于有向图，如果该图是欧拉图，则必须满足以下两个条件：

1. 图是强连通的
2. 每个节点的入度和出度相等

因此，我们可以使用关联矩阵来判断一个图是否为欧拉图：

#include <stdio.h>

#define MAXN 100 // 最多有100个节点
#define MAXM 10000 // 最多有10000条边

int n, m; // 节点数和边数
int degree[MAXN]; // 每个节点的度数
int matrix[MAXN][MAXM]; // 关联矩阵

int is_euler() {
    int i, j, cnt = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (matrix[i][j]) { // 如果第i个节点和第j条边相连
                degree[i]++; // 第i个节点的度数+1
                degree[j]++; // 第j条边的度数+1
            }
        }
    }
    for (i = 0; i < n; i++) {
        if (degree[i] % 2 == 1) { // 如果有度数为奇数的节点
            return 0; // 不是欧拉图
        }
        if (degree[i] != 0) { // 如果该节点有边相连
            cnt++; // 连通块数+1
        }
    }
    if (cnt > 1) { // 如果有多个连通块
        return 0; // 不是欧拉图
    }
    return 1; // 是欧拉图
}

int main() {
    scanf("%d%d", &n, &m);
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            matrix[i][j] = 0; // 初始化关联矩阵
        }
        degree[i] = 0; // 初始化每个节点的度数为0
    }
    for (i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        matrix[u][i] = 1; // 第i条边与第u个节点相连
        matrix[v][i] = 1; // 第i条边与第v个节点相连
    }
    if (is_euler()) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

上述代码中，我们使用了一个数组 `degree` 来存储每个节点的度数，其中 `degree[i]` 表示第 `i` 个节点的度数。同时，我们使用了一个二维数组 `matrix` 来存储关联矩阵，其中 `matrix[i][j]` 表示第 `i` 个节点和第 `j` 条边是否相连。在 `is_euler` 函数中，我们首先遍历整个关联矩阵，计算每个节点的度数。然后，我们遍历每个节点，判断其度数是否为偶数，如果有度数为奇数的节点，那么该图就不是欧拉图。最后，我们判断该图是否是连通的，如果有多个连通块，那么该图也不是欧拉图。