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

思路判断图是否连通且度数为偶数。可以使用DFS或BFS遍历图，判断是否能够遍历到所有节点，同时统计每个节点的度数，最后判断是否所有节点的度数都为偶数。注意要在每个测试用例结束后清空数据。

参考代码

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

int n, m;
int graph[MAXN][MAXN];
int visited[MAXN];
int degree[MAXN];

void dfs(int u) {
    visited[u] = 1;
    for (int v = 1; v <= n; v++) {
        if (graph[u][v] && !visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    while (scanf('%d %d', &n, &m) != EOF && n != 0) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j] = 0;
            }
            visited[i] = 0;
            degree[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf('%d %d', &u, &v);
            graph[u][v] = graph[v][u] = 1;
            degree[u]++;
            degree[v]++;
        }
        dfs(1);
        int flag = 1;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                flag = 0;
                break;
            }
            if (degree[i] % 2 != 0) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            printf('YES\n');
        } else {
            printf('NO\n');
        }
    }
    return 0;
}