欧拉图问题C语言

欧拉图问题是指判断一个图中是否存在一条通过所有边恰好一次的路径或回路。在C语言中可以使用邻接矩阵或邻接表表示图，并通过深度优先搜索或广度优先搜索判断图是否为欧拉图。

以下是使用邻接矩阵和深度优先搜索判断图是否为欧拉图的示例代码：

#include <stdio.h>
#define MAXN 100

int G[MAXN][MAXN];  // 邻接矩阵表示图
int vis[MAXN];      // 标记数组，记录节点是否被访问过

int dfs(int u, int n) {
    vis[u] = 1;  // 标记当前节点已被访问
    int cnt = 1;  // 统计当前连通块的节点数
    for (int v = 0; v < n; v++) {
        if (G[u][v] && !vis[v])  // 如果u和v有边相连且v未被访问
            cnt += dfs(v, n);    // 继续搜索v所在连通块
    }
    return cnt;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);  // 输入节点数和边数
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);  // 输入每条边的起点和终点
        G[u][v] = G[v][u] = 1;  // 标记这条边
    }
    int cnt = dfs(0, n);       // 统计从节点0开始所在的连通块的节点数
    if (cnt != n) {            // 如果不是连通图，就不可能存在欧拉回路或欧拉路径
        printf("Not Eulerian\n");
        return 0;
    }
    int odd = 0;  // 统计度数为奇数的节点数
    for (int i = 0; i < n; i++) {
        int degree = 0;  // 当前节点的度数
        for (int j = 0; j < n; j++) {
            if (G[i][j]) degree++;  // 统计i的度数
        }
        if (degree % 2 == 1) odd++;  // 如果度数为奇数，计数器加1
    }
    if (odd == 0) {
        printf("Eulerian circuit\n");  // 所有节点的度数均为偶数，存在欧拉回路
    } else if (odd == 2) {
        printf("Eulerian path\n");  // 只有两个节点的度数为奇数，存在欧拉路径
    } else {
        printf("Not Eulerian\n");  // 其他情况都不是欧拉图
    }
    return 0;
}

在输入中，第一个整数为节点数，第二个整数为边数，接下来m行每行输入两个整数表示一条边的起点和终点。输出结果有三种情况：欧拉回路、欧拉路径和不是欧拉图。