欧拉回路判定算法·一笔画问题

本文主要是介绍欧拉回路判定算法·一笔画问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果图中的一条路经经过每条边一次，则该路径称为欧拉路径。
如果该路径正好是一个回路，即从起点出发又回到起点，则该路径称为欧拉回路。
如果一个图有欧拉回路，则该图称为欧拉图。

无向图存在欧拉回路的充要条件
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。
无向图存在欧拉路径的充要条件
当且仅当该图顶点度数为奇数的点的个数为0或者2。

欧拉定理二：
如果一个无向图有2n个奇顶点，那么它至少需要n笔画成。

有向图存在欧拉回路的充要条件
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

题目

题目描述
欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。
输出描述:
每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

#include <stdio.h>
#include <string.h>int main()
{int n,m,degree[1001],s,t,flag;while(~scanf("%d",&n)){if(n!=0){scanf("%d",&m);flag = 1;memset(degree,0,sizeof(int)*(n+1));for(int i = 0;i<m;i++){scanf("%d %d",&s,&t);degree[s]++;degree[t]++;}for(int i = 1;i<=n;i++){if(degree[i]%2!=0) flag = 0;}printf("%d\n",flag);}else break;}return 0;
}