C语言一笔画问题：判断图是否可一笔画

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

思路

判断图是否连通且每个点的度数都是偶数。可以用并查集判断图的连通性，用一个数组记录每个点的度数，最后遍历一遍数组判断每个点的度数是否都是偶数。

注意

• 输入可能包含多组数据，需要多组数据循环读入和输出。
• 并查集的初始化需要在每组数据开始时进行。

参考代码

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

#define MAXN 1000

int father[MAXN];
int degree[MAXN];

// 初始化并查集
void init(int n) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        degree[i] = 0;
    }
}

// 查找根节点
int find(int x) {
    if (father[x] != x) {
        father[x] = find(father[x]);
    }
    return father[x];
}

// 合并两个节点
void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        father[fx] = fy;
    }
}

int main() {
    int n, m, u, v;
    while (scanf('%d %d', &n, &m) != EOF && n != 0) {
        init(n); // 初始化并查集
        // 读取边信息并更新度数
        for (int i = 0; i < m; i++) {
            scanf('%d %d', &u, &v);
            degree[u]++;
            degree[v]++;
            merge(u, v);
        }
        // 判断图是否连通
        int root = find(1);
        int flag = 1;
        for (int i = 2; i <= n; i++) {
            if (find(i) != root) {
                flag = 0;
                break;
            }
        }
        // 判断每个点的度数是否都是偶数
        for (int i = 1; i <= n; i++) {
            if (degree[i] % 2 != 0) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            printf('YES\n');
        } else {
            printf('NO\n');
        }
    }
    return 0;
}