C语言实现一笔画游戏判断

题目描述 我们现在玩一个游戏，名字就取作一笔画吧，规则是这样的：有一个连通的图，笔不离开纸面，可画过图中每条边仅一次，而且每条边都要画过一次，且可以回到起点，成功就是一笔画了。

输入测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。

输出每个测试用例的输出占一行，若能成功一笔画则输出YES，否则输出NO。

样例输入 3 3 1 2 2 3 1 3 0 0

样例输出 YES

解题思路

题目要求判断给出的无向图是否可以成为欧拉回路，即只要每个点的度数都为偶数，就可以成为欧拉回路。

因为无向图中的边是双向的，所以建图时要将两个方向都建出来。

如果没有欧拉回路，还要判断是否可以成为欧拉路径，即只有两个点的度数为奇数，其余点的度数都为偶数。

本题需要多组数据输入，所以要用 while 循环，当输入的节点数为 0 时结束。

AC代码

#include <stdio.h>

int main() {
    int N, M, u, v, degree[1001] = {0};
    while (scanf("%d %d", &N, &M) != EOF && N != 0) {
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &u, &v);
            degree[u]++;
            degree[v]++;
        }
        int odd_count = 0;
        for (int i = 1; i <= N; i++) {
            if (degree[i] % 2 != 0) {
                odd_count++;
            }
        }
        if (odd_count == 0) {
            printf("YES\n");
        } else if (odd_count == 2) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
        // 清空度数数组
        for (int i = 1; i <= N; i++) {
            degree[i] = 0;
        }
    }
    return 0;
}